Lt15. 三数之和、18. 四数之和

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

采用排序加双指针解决。

1. 将数组由小到大排序。
2. 首先判断第一个元素是否小于 0，如果小于 0 则不存在解。
3. 再判断数组是否同符号，即第一个小于等于 0，最后一个大于等于 0，如果同符号，则不存在解。
4. 进行循环，设置左指针为当前指针加一，右指针为数组最后一个数，如果当前的数和上一个数相等，跳过该数，避免重复。
5. while 循环，计算当前指针，左指针，右指针的和：
   1. 等于 0，加入结果数组，并将左、右指针分别向右移、左移，直到指向下一个不同的数
   2. 大于 0，将右指针向左移，直到指向下一个不同的数
   3. 小于 0，将左指针向右移，直到指向下一个不同的数
   4. 当左指针和右指针相遇时，跳出循环

解答

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums = nums.sort((a, b) => a - b);
  let res = [];
  if (nums[0] <= 0 && nums[nums.length - 1] >= 0) {
    for (let i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) continue;
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        let sum = nums[i] + nums[left] + nums[right];
        if (sum === 0) {
          res.push([nums[i], nums[left], nums[right]]);
          while (nums[left] === nums[++left] && left < right) {}
          while (nums[right] === nums[--right] && left < right) {}
        } else if (sum < 0) {
          while (nums[left] === nums[++left] && left < right) {}
        } else if (sum > 0 && left < right) {
          while (nums[right] === nums[--right] && left < right) {}
        } else {
          break;
        }
      }
    }
  }
  return res;
};

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

思路

将 4 数之和的问题转为 3 数之和，再采用 3 数之和的排序加双指针来解决。重点和难点是如何进行 4 数之和的减枝操作，避免超时。

1. 判断数组个数，小于 4 的话返回空数组。
2. 将数组由小到大排序。
3. 确认第一个数，减枝过程如下：
   1. 如果当前的数和上一个数相等，跳过该数，避免重复
   2. 如果排序后前四个数之和大于 target，不存在结果，直接返回空数组
   3. 如果当前数和最后三个数之和小于 target，则中间不可能存在一个组合等于 target，跳过该数，求下一个数
4. 减枝后，则确定取该数为第一个数，确定新的newTarget值为target - nums[i]，j 为 i+1
5. 接下来的操作和求 3 数之和相同：进行循环，设置左指针为当前指针加一，右指针为数组最后一个数，如果当前的数和上一个数相等，跳过该数，避免重复。
6. while 循环，计算当前指针，左指针，右指针的和：
   1. 等于 0，加入结果数组，并将左、右指针分别向右移、左移，直到指向下一个不同的数
   2. 大于 0，将右指针向左移，直到指向下一个不同的数
   3. 小于 0，将左指针向右移，直到指向下一个不同的数
   4. 当左指针和右指针相遇时，跳出循环
7. 进行循环，设置左指针为当前指针加一，右指针为数组最后一个数，如果当前的数和上一个数相等，跳过该数，避免重复。
8. while 循环，计算当前指针，左指针，右指针的和：
   1. 等于 0，加入结果数组，并将左、右指针分别向右移、左移，直到指向下一个不同的数
   2. 大于 0，将右指针向左移，直到指向下一个不同的数
   3. 小于 0，将左指针向右移，直到指向下一个不同的数
   4. 当左指针和右指针相遇时，跳出循环

解答

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  let res = [];
  if (nums.length < 4) return res;
  nums = nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
    if (
      nums[i] +
        nums[nums.length - 3] +
        nums[nums.length - 2] +
        nums[nums.length - 1] <
      target
    )
      continue;

    const newTarget = target - nums[i];

    for (let j = i + 1; j < nums.length - 2; j++) {
      if (j > i + 1 && nums[j] == nums[j - 1]) continue;
      let left = j + 1;
      let right = nums.length - 1;
      while (left < right) {
        let sum = nums[j] + nums[left] + nums[right];
        if (sum === newTarget) {
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          while (nums[left] === nums[++left] && left < right) {}
          while (nums[right] === nums[--right] && left < right) {}
        } else if (sum < newTarget) {
          while (nums[left] === nums[++left] && left < right) {}
        } else if (sum > newTarget && left < right) {
          while (nums[right] === nums[--right] && left < right) {}
        } else {
          break;
        }
      }
    }
  }
  return res;
};