算法 - 三数之和 (3Sum)

Posted on

1. 题目

给你一个整数数组 nums，找出所有满足 nums[i] + nums[j] + nums[k] == 0 的三元组 [i, j, k]，且要求：

  • i、j、k 两两不同。
  • 返回的三元组不能重复。

示例:

1
2
3
输入: nums = [-1, 0, 1, 2, -1, -4]
输出: [[-1, -1, 2], [-1, 0, 1]]
解释: 满足条件的不重复三元组如上，注意 [-1, 0, 1] 和 [0, 1, -1] 视为同一个。

2. 解题思路

暴力三重循环是 O(n³) 且难以去重。经典做法是排序 + 双指针，把复杂度降到 O(n²)。

  1. 排序：nums.sort((a, b) => a - b)，让双指针成为可能，也让重复值相邻便于跳过。
  2. 固定一个数：外层枚举 nums[i]，把问题转化为「在 i 右侧找两数之和等于 -nums[i]」——退化成 [两数之和 II（有序）]。
  3. 双指针夹逼：left = i + 1，right = n - 1：
    • sum === 0 → 记录答案，然后左右指针同时向内移动并跳过重复。
    • sum < 0 → 需要更大的数，left++。
    • sum > 0 → 需要更小的数，right--。
  4. 三处去重：
    • i 与前一个相同则跳过（避免重复的第一个数）。
    • 命中答案后，left、right 各自跳过相同值。

优化剪枝：排序后若 nums[i] > 0，三数之和不可能为 0，直接结束。

  • 时间复杂度：O(n²)。
  • 空间复杂度：O(log n)（排序栈空间，不计输出）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function threeSum(nums: number[]): number[][] {
    const res: number[][] = [];
    const n = nums.length;
    nums.sort((a, b) => a - b);

    for (let i = 0; i < n - 2; i++) {
        // 剪枝：最小值已大于 0，不可能凑出 0
        if (nums[i] > 0) break;
        // 去重：跳过相同的第一个数
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1;
        let right = n - 1;

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

            if (sum === 0) {
                res.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 res;
}

// 测试
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]
console.log(threeSum([0, 0, 0, 0])); // [[0, 0, 0]]

4. 面试延伸

  • 扩展到 k-Sum？ 排序后递归地固定 k-2 个数，最后两数用双指针，通用模板时间 O(n^{k-1})。
  • 最接近的三数之和（LeetCode 16）？ 同样双指针，只是记录过程中 |sum - target| 的最小值。
  • 去重是最大坑点：一定要在push之后跳过重复，而不是用 Set 序列化数组去重（后者能过但脏）。

难度：中等 | LeetCode 15 题 | 双指针标杆题