四数之和

题目

直接看 15. 三数之和 即可, 做了一个通用解法, 可以处理 nSum 问题.

提示:

• 1 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

示例

输入: nums = [1, 0, -1, 0, -2, 2], target = 0

输出: [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0 ,2]]

题解

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => a - b)
  return nSum(nums, 4, 0, target)
}

/**
 * @param {number[]} nums
 * @param {number} n
 * @param {number} start
 * @param {number} target
 * @return {number[][]}
 */
var nSum = function (nums, n, start, target) {
  const len = nums.length
  const res = []

  // 提前过滤掉一些不可能的情况
  // 至少是 2Sum, 且数组大小不应该小于 n
  if (n < 2 || len < n) return res

  if (n === 2) {
    let low = start
    let high = len - 1

    while (low < high) {
      const lowVal = nums[low]
      const highVal = nums[high]
      const sum = lowVal + highVal

      if (sum < target) {
        while (low < high && nums[low] === lowVal) low++
      } else if (sum > target) {
        while (low < high && nums[high] === highVal) high--
      } else {
        res.push([lowVal, highVal])
        while (low < high && nums[low] === lowVal) low++
        while (low < high && nums[high] === highVal) high--
      }
    }
  } else {
    // n > 2 时, 递归计算 (n-1)Sum 的结果
    for (let i = start; i < len; i++) {
      const items = nSum(nums, n - 1, i + 1, target - nums[i])

      for (const item of items) {
        // (n-1)Sum 加上 nums[i] 就是 nSum
        item.push(nums[i])
        res.push(item)
      }

      while (i < len - 1 && nums[i] === nums[i + 1]) i++
    }
  }

  return res
}