给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target
  • 你可以按 任意顺序 返回答案 。

思路

  1. 与 《三数之和》 类似，多维护一个循环层级即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
var fourSum = function (nums, target) {
  if (nums.length < 4) {
    return []
  }
  const result = []
  nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length - 3; ++i) {
    const iVal = nums[i]
    if (i > 0 && nums[i - 1] === iVal) {
      continue
    }
    for (let j = i + 1; j < nums.length - 2; ++j) {
      const jVal = nums[j]
      if (j > i + 1 && nums[j - 1] === jVal) {
        continue
      }
      let k = j + 1
      let l = nums.length - 1
      while (k < l) {
        const kVal = nums[k]
        const lVal = nums[l]
        const sum = iVal + jVal + kVal + lVal
        if (sum < target) {
          ++k
        } else if (sum > target) {
          --l
        } else {
          result.push([iVal, jVal, kVal, lVal])
          while (k < l && nums[k] === kVal) {
            ++k
          }
          while (k < l && nums[l] === lVal) {
            --l
          }
        }
      }
    }
  }
  return result
}