leetcode #18 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

• 题目大意
  给定一组整数，找到数组中所有相加等于target的4个数，结果中不能有相同的一组。
  与之前的3Sum 算法完全一样，只是多加了一层循环，时间复杂度由O(n²) 变为 O(n³)

除此之外，我还加上了两个剪枝，当可能选出来的最小的4个数已经比target大了或者当可能选出来的4个最大数比target还小，就可以跳过此次枚举。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
const fourSum = function (nums, target) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 3; i++) {
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;  //可能得到的最小值比target还要大
    if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) continue;  //可能得到的最大值比target还要小
    if (i > 0 && nums[i] === nums[i - 1]) { // 跳过相同的值
      continue;
    }
    for (let l = i + 1; l < nums.length - 2; l++) {
      if (nums[i] + nums[l + 1] + nums[l + 2] + nums[l] > target) break;
      if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[l] < target) continue;
      if (l > i + 1 && nums[l] === nums[l - 1]) { // 跳过相同的值
        continue;
      }
      let j = l + 1;
      let k = nums.length - 1;
      const rest = target - nums[i] - nums[l];
      while (j < k) {
        if (nums[j] + nums[k] === rest) {
          result.push([nums[i], nums[l], nums[j], nums[k]]);
          while (j < k && nums[j] === nums[j + 1]) j++; // 跳过相同的值
          while (j < k && nums[k] === nums[k - 1]) k--;
          j++;
          k--;
        } else if (nums[j] + nums[k] > rest) k--; // 如果两数相加比剩余的值大，减小较大的值
        else {
          j++; // 否则增加较小的值
        }
      }
    }
  }
  return result;
};