三数之和：排序与双指针

15. ⭐️​三数之和

题目描述 中等 数组 双指针 排序

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

提示 答案中不可以包含重复的三元素。

示例 1：

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。
不同的三元组是 [-1, 0, 1] 和 [-1, -1, 2]

示例 2：

输入：nums = [0, 1 ,1]
输出：[]
解释：唯一可能的三元组和不为 0。

示例 3：

输入：nums = [0, 0, 0] 输出：[[0, 0, 0]] 解释：唯一可能的三元组和为 0。

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

思路

nSum 系列问题的核心思路就是排序+双指针。

先给数组从小到大排序，然后双指针 left 和 right 分别在数组开头和结尾，这样就可以控制 nums[left] 和 nums[right] 这个两数之和的大小：

如果你想让它俩的和大一些，就让 left++，如果你想让它俩的和小一些，就让 right--。

基于两数之和可以得到一个万能函数 nSumTarget，扩展出 n 数之和的解法。

解法代码

画手大鹏解法 双指针

• 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i] 后面的两段，数字分别为 nums[left] 和 nums[right]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集。
• 如果 nums[i] 大于 0，则三数之和必然无法等于 0，结束循环
• 如果 nums[i] == nums[i - 1]，则说明该数字重复，会导致结果重复，所以应该跳过。
• 当 sum == 0 时，nums[left] == nums[left + 1] 则会导致结果重复，应该跳过，left++
• 当 sum == 0 时，nums[right] == nums[right - 1] 则会导致结果重复，应该跳过，right--
• 时间负责度：O(n^2)，n 为数组长度

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  let ans = [];
  const len = nums.length;
  if(nums == null || len < 3) {
    return ans;
  }
  nums.sort((a, b) => a - b); // 排序
  for (let i = 0; i < len ; i++) {
    if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
    if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
    let left = i + 1;
    let right = len - 1;
    while(left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if(sum == 0) {
        ans.push([nums[i],nums[left],nums[right]]);
        while (left < right && nums[left] == nums[left+1]) left++; // 去重
        while (left < right && nums[right] == nums[right-1]) right--; // 去重
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      }
    }
  }
  return ans;
};