LeetCode题解：18. 四数之和，双指针，JavaScript，详细注释

[chencl1986]

原题连接：https://leetcode-cn.com/problems/4sum/

解题思路：

1. 该题是15. 三数之和的进阶版，如果你对三数之和不熟悉，可以先参考我的题解LeetCode题解：15. 三数之和，JavaScript双循环+双指针，详细注释。
2. 使用双指针，可以在一次循环中，找到两数之和。具体做法是使用两个指针从两端向中间推进，每推进一次都计算两数之和，如果小于目标值，表示左指针太小，把左指针向右移动，知道值出现变化，再次计算两数之和。右指针也进行同样操作。
3. 如果两数之和等于目标值，则记录结果。之后将两个指针同时想中间移动，直到出现新的值，再重复步骤2、3。
4. 利用两次循环，分别找到四元组集合的前两个值，再用双指针找到后两个值，即可组成相应结果。
5. 去重的大原则是将数组排序，这样相同的值就排列在一起，只要第一个值已被使用过，就可以认为它对应的结果已被生成，这样只要通过nums[i] === nums[i - 1]即可排除掉相等的值。
6. 需要注意的测试用例：

[0,0,0,0]
0

[-5,5,4,-3,0,0,4,-2]
4

[1,-2,-5,-4,-3,3,3,5]
-11

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  // 去重时要对比前后两个值是否相等，排序保证对比能正常生效
  nums.sort((a, b) => a - b);
  // 存储结果
  let result = [];

  for (let i = 0; i < nums.length - 3; i++) {
    // 如果有连续数个值相等，在第一遍循环中，第一个值对应的可能解都已被生成过，之后的值都可以跳过
    if (nums[i] === nums[i - 1]) {
      continue;
    }

    // 缓存第一级的target，提供给下一层循环使用
    let firstTarget = target - nums[i];

    for (let j = i + 1; j < nums.length - 2; j++) {
      // 如果有连续数个值相等，在当前循环中，先保证第一个值的解会被生成，之后的值都可以跳过
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue;
      }

      // 缓存第二级的target，提供给下一层循环使用
      let secondTarget = firstTarget - nums[j];

      // 使用两个指针，分别从数组剩余部分的首尾向中间推进，查找符合条件的结果
      let k = j + 1;
      let l = nums.length - 1;

      // 当k等于l时，完成遍历，退出循环
      while (k < l) {
        // 获取k和l对应值之和
        const sum = nums[k] + nums[l];

        // 但sum小于secondTarget时，表示nums[k]太小，需要移动k指针，知道遇到新的nums[k]
        if (sum < secondTarget) {
          k++;
          while (nums[k] === nums[k - 1]) {
            k++;
          }
        }

        // 但sum小于secondTarget时，表示nums[l]太小，需要移动k指针，知道遇到新的nums[kl]
        if (sum > secondTarget) {
          l--;
          while (nums[l] === nums[l + 1]) {
            l--;
          }
        }

        // 但sum等于secondTarget时，表示找到了符合条件的四元组
        if (sum === secondTarget) {
          // 将四元组存入result
          result.push([nums[i], nums[j], nums[k], nums[l]]);

          // 为避免找到重复结果，需要移动k和l指针，直到遇到新值
          k++;
          while (nums[k] === nums[k - 1]) {
            k++;
          }
          l--;
          while (nums[l] === nums[l + 1]) {
            l--;
          }
        }
      }
    }
  }

  return result;
};