15. 三数之和

LeetCode 原题链接

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]，满足：

  • i、j、k 互不相同
  • nums[i] + nums[j] + nums[k] === 0

请你返回所有和为 0 且不重复的三元组。

示例：

输入: nums = [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]
输入: nums = [0,1,1]
输出: []
输入: nums = [0,0,0]
输出: [[0,0,0]]

1. 题型判断

本题要求找出所有不重复的三元组，使三数之和等于 0。

直接三层循环会达到 O(n^3)，效率太低。可以先对数组排序，固定第一个数 nums[i]，再在右侧区间里用左右指针寻找另外两个数。

排序后，左右指针可以根据当前三数之和的大小决定移动方向：

  • 和太小，说明需要更大的数，移动 left。
  • 和太大，说明需要更小的数，移动 right。

所以这是一道典型的排序 + 双指针题。

2. 指针含义

排序后，固定一个下标 i，在区间 [i + 1, nums.length - 1] 中寻找另外两个数。

  • i：固定的第一个数下标。
  • left：从 i + 1 开始，指向第二个数。
  • right：从数组末尾开始，指向第三个数。
  • ans：保存所有不重复的三元组。

当前检查的三元组是：

[nums[i], nums[left], nums[right]]

3. 窗口或区间维护规则

先对 nums 升序排序。

对于每个固定下标 i：

  • 如果 nums[i] > 0，由于后面的数都大于等于 nums[i]，三数之和一定大于 0，可以直接结束。
  • 如果 i > 0 且 nums[i] === nums[i - 1]，说明这个固定值已经处理过，跳过，避免重复答案。
  • 设置 left = i + 1，right = nums.length - 1。

在 left < right 时计算：

const sum = nums[i] + nums[left] + nums[right];

根据 sum 移动指针：

  • sum === 0：找到一个合法三元组，记录答案，然后同时移动 left 和 right，并跳过重复值。
  • sum < 0：当前和太小，需要更大的数，left++。
  • sum > 0：当前和太大，需要更小的数，right--。

4. 答案更新时机

本题要求所有不重复三元组，所以只有当 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--;

这样可以避免类似 [-1, 0, 1] 被重复加入。

5. 边界条件与易错点

边界条件：

  • 如果 nums.length < 3，不可能组成三元组，返回空数组。
  • 如果排序后 nums[i] > 0，后续不可能再得到和为 0 的三元组，可以提前结束。
  • 如果数组中有多个 0，例如 [0, 0, 0, 0]，只能返回一个 [0, 0, 0]。

易错点：

  • 必须先排序，否则无法根据 sum 大小决定指针移动方向。
  • 固定下标 i 时要去重：i > 0 && nums[i] === nums[i - 1]。
  • 找到合法三元组后，左右指针都要去重，否则结果会重复。
  • 不要在找到答案前随意跳过 left 或 right，否则可能漏掉合法组合。

6. 代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const ans = [];

  if (nums.length < 3) {
    return ans;
  }

  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) {
      break;
    }

    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) {
        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 {
        right--;
      }
    }
  }

  return ans;
};

7. 复杂度分析

  • 时间复杂度：O(n^2)。排序需要 O(n log n)，外层固定一个数，内层左右指针整体最多移动 O(n) 次，总体为 O(n^2)。
  • 空间复杂度：O(1)。不计入返回结果数组，额外只使用了常数个变量；排序产生的栈空间取决于语言实现。