Skip to content
On this page

18. 四数之和

给你一个由 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:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

提示:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  var res = [],
    len = nums.length
  nums.sort((a, b) => a - b)
  for (var a = 0; a <= len - 4; a++) {
    if (a >= 1 && nums[a] === nums[a - 1]) continue
    for (var b = a + 1; b <= len - 3; b++) {
      if (b > a + 1 && nums[b] === nums[b - 1]) continue
      var c = b + 1,
        d = len - 1
      while (c < d) {
        var sum = target - nums[a] - nums[b] - nums[c] - nums[d]
        if (sum > 0) {
          c++
        } else if (sum < 0) {
          d--
        } else {
          res.push([nums[a], nums[b], nums[c], nums[d]])
          while (c < d && nums[c] === nums[c + 1]) c++
          while (c < d && nums[d] === nums[d - 1]) d--
          c++
          d--
        }
      }
    }
  }
  return res
}

console.log(fourSum([1, 0, -1, 0, -2, 2], 0))
console.log(fourSum([2, 2, 2, 2, 2], 8))
console.log(fourSum([-2, -1, -1, 1, 1, 2, 2], 0))