三数之和

1. 题目呈现

难度等级：🟡 中等
核心考察点：数组、双指针、排序

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

2. 解题思路拆解

方法：排序 + 双指针

这道题如果使用三重循环暴力求解，复杂度会达到 $O(n^3)$，肯定会超时。我们可以利用排序来降低复杂度。

排序：首先对数组进行升序排序。排序的好处是方便我们移动指针来调整和的大小，同时也方便去重。
固定一个数：遍历数组，固定第一个数 nums[i]。
- 如果 nums[i] > 0，因为数组已排序，后面的数肯定也都大于 0，不可能凑出和为 0 的三元组，直接 break。
- 去重：如果 i > 0 且 nums[i] == nums[i-1]，说明这个数刚才已经作为第一个数处理过了，跳过以避免重复。
双指针寻找另外两个数：
- 设左指针 L = i + 1，右指针 R = n - 1。
- 计算 sum = nums[i] + nums[L] + nums[R]。
- 情况 1：sum == 0。找到一组解，加入结果集。
  - 去重：L 向右移动，跳过所有重复的 nums[L]。
  - 去重：R 向左移动，跳过所有重复的 nums[R]。
  - L 和 R 继续向中间移动。
- 情况 2：sum < 0。说明和太小了，需要让和变大，所以 L 向右移。
- 情况 3：sum > 0。说明和太大了，需要让和变小，所以 R 向左移。

这种方法将复杂度降低到了 $O(n^2)$。

3. 代码实现

javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if (nums == null || len < 3) return ans;

    // 1. 排序
    nums.sort((a, b) => a - b);

    // 2. 遍历第一个数
    for (let i = 0; i < len; i++) {
        // 如果当前数字大于0，则三数之和一定大于0，结束循环
        if (nums[i] > 0) break;

        // 去重：如果当前数字和前一个一样，跳过
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        let L = i + 1;
        let R = len - 1;

        while (L < R) {
            const sum = nums[i] + nums[L] + nums[R];
            if (sum == 0) {
                ans.push([nums[i], nums[L], nums[R]]);
                
                // 去重：跳过重复的 L
                while (L < R && nums[L] == nums[L + 1]) L++;
                // 去重：跳过重复的 R
                while (L < R && nums[R] == nums[R - 1]) R--;
                
                L++;
                R--;
            } else if (sum < 0) {
                // 和太小，L 右移
                L++;
            } else if (sum > 0) {
                // 和太大，R 左移
                R--;
            }
        }
    }
    return ans;
};

代码执行演示

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

排序：[-4, -1, -1, 0, 1, 2]
i=0, nums[i]=-4：
- L=-1 (idx 1), R=2 (idx 5)。Sum = -4 - 1 + 2 = -3 < 0。L 右移。
- L=-1 (idx 2), R=2 (idx 5)。Sum = -4 - 1 + 2 = -3 < 0。L 右移。
- ... 直到 L >= R。无解。
i=1, nums[i]=-1：
- L=-1 (idx 2), R=2 (idx 5)。Sum = -1 - 1 + 2 = 0。找到解 [-1, -1, 2]。
  - L 跳过重复值移至 0 (idx 3)。R 移至 1 (idx 4)。
- L=0 (idx 3), R=1 (idx 4)。Sum = -1 + 0 + 1 = 0。找到解 [-1, 0, 1]。
  - L, R 移动后相遇，退出。
i=2, nums[i]=-1：
- 和前一个数重复，continue 跳过。
i=3, nums[i]=0：
- L=1, R=2。Sum = 3 > 0。无解。
i=4, nums[i]=1：
- 1 > 0，循环结束。

最终结果：[[-1, -1, 2], [-1, 0, 1]]。

4. 复杂度分析

维度	描述
时间复杂度	$O(n^2)$。排序耗时 $O(n \log n)$，双指针遍历耗时 $O(n^2)$，总体为 $O(n^2)$。
空间复杂度	$O(\log n)$。取决于排序算法的栈空间开销。如果不考虑结果数组，可以认为是 $O(1)$ 或 $O(\log n)$。

三数之和 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：排序 + 双指针 ​

3. 代码实现 ​

代码执行演示 ​