三数之和

题目描述

给你一个整数数组 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

我的解题过程

方法一：排序 + 双指针

依次固定一个数，然后使用双指针在剩下的数组中寻找两个数，使得三数之和为 0。

function threeSum(nums: number[]): number[][] {
  let res = [];
  nums = nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        res.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;
      }
    }
  }

  return res;
}

运行报错了 发现有重复的结果，需要在添加结果前进行去重处理：

function threeSum(nums: number[]): number[][] {
  let res = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    // 重复的维度跳过
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        res.push([nums[i], nums[left], nums[right]]);

        // 如果下一个是相同的值那么会有重复数据
        while (nums[left] === nums[left + 1]) left++;
        while (nums[right] === nums[right - 1]) right--;

        left++;
        right--;
      }
    }
  }

  return res;
}

解题思路

核心逻辑：

三数之和问题可以转化为固定一个数，然后在剩余数组中寻找两个数使得三数之和为 0。关键点：

1. 先对数组排序，便于使用双指针和去重
2. 固定第一个数 nums[i]，在 i 之后的数组中用双指针寻找另外两个数
3. 如果 nums[i] > 0，由于数组已排序，后面的数都大于 0，不可能找到和为 0 的三元组，直接结束
4. 去重处理：对于重复的数字要跳过，避免结果中出现重复的三元组

算法步骤：

1. 对数组进行升序排序
2. 遍历数组，固定第一个数 nums[i]（i 从 0 到 length-2）
3. 如果 nums[i] 与前一个数相同，跳过以避免重复
4. 设置双指针：left = i+1，right = length-1
5. 当 left < right 时：
   • 计算三数之和 sum = nums[i] + nums[left] + nums[right]
   • 如果 sum < 0，left++
   • 如果 sum > 0，right--
   • 如果 sum == 0，找到一组解，加入结果集，然后移动左右指针并跳过重复值
6. 返回结果集

去重策略：

• 对于第一个数：如果与前一个数相同则跳过
• 对于第二、三个数：找到解后，移动指针时跳过所有相同的值