LeetCode 15：三数之和（3Sum）题解

3Sum 是 LeetCode Hot 100 中非常经典的一道题。

这道题表面上看是在数组中找三个数，让它们的和等于 0。如果一开始直接按照最朴素的想法去做，很多人都会想到三层循环，把所有三元组全部枚举一遍，然后筛出满足条件的答案。

这种方法当然可以得到结果，但时间复杂度是 O(n^3)，效率太低，在实际提交时很难通过。

所以这道题真正想考察的，其实是两件事：

• 排序之后如何使用双指针

• 如何在查找过程中进行去重

你给出的这份 Java 代码，就是这道题最经典、最标准的写法之一。 本文就结合这段代码，系统地讲一下三数之和的解题思路。

题目介绍

给你一个整数数组 nums，请你判断是否存在三个元素 a、b、c，使得：

a + b + c = 0

你需要找出 所有不重复 的三元组，并返回它们。

注意这里有两个关键点：

1. 三个数的和必须等于 0

2. 返回的三元组不能重复

比如：

• [-1, 0, 1] 和 [0, -1, 1] 本质上是同一个三元组

• 如果数组里有多个相同数字，也不能让结果集中出现重复答案

这就是这道题的难点所在。

示例

示例 1

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

解释一下这个结果：

• -1 + -1 + 2 = 0

• -1 + 0 + 1 = 0

并且这两个三元组互不重复，所以最终返回它们。

示例 2

输入：nums = [0,1,1]
输出：[]

因为无论怎么选三个数，它们的和都不可能等于 0。

示例 3

输入：nums = [0,0,0]
输出：[[0,0,0]]

虽然数组里有三个 0，并且它们确实能组成和为 0 的三元组，但答案里只需要保留一个：

[0,0,0]

暴力思路为什么不行？

如果完全不做优化，那么最直接的方法就是三层循环：

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                // 加入答案
            }
        }
    }
}

这种做法的时间复杂度是：

O(n^3)

如果数组长度比较大，效率会很差。

而且就算你暴力枚举出所有结果，还得继续想办法去重，这又会让代码变得更麻烦。

所以这道题更优的做法是：

排序 + 固定一个数 + 双指针

这也是你这段代码的核心思想。

核心思路

第一步：先排序

Arrays.sort(nums);

排序有两个非常重要的作用：

1. 方便使用双指针

2. 方便去重

排序之后，数组从小到大排列。这样我们固定第一个数后，就可以把剩下的部分看作一个“有序数组中的两数之和”问题。

这一步是整道题的基础。

第二步：枚举第一个数

我们用一个 for 循环，依次固定三元组中的第一个数 nums[i]。

剩下的任务就变成：

在区间 [i+1, n-1] 中找两个数，让它们的和等于 -nums[i]

这就和经典的“两数之和（有序版）”非常像了，因此可以使用双指针。

第三步：双指针查找剩下两个数

固定了 nums[i] 以后：

• 左指针 lo = i + 1

• 右指针 hi = nums.length - 1

目标值是：

sum = 0 - nums[i]

接下来判断：

• 如果 nums[lo] + nums[hi] == sum，说明找到一个三元组

• 如果 nums[lo] + nums[hi] < sum，说明和太小了，需要让左指针右移

• 如果 nums[lo] + nums[hi] > sum，说明和太大了，需要让右指针左移

这样就能在线性时间内完成查找。

Java 代码

下面就是你给出的代码，我这里保持原始逻辑，并加上注释方便理解：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 先排序，方便双指针和去重
        Arrays.sort(nums);

        List<List<Integer>> res = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            // 如果当前数已经大于 0，后面不可能再凑出 0，直接结束
            if (nums[i] > 0) break;

            // 去重：避免第一个数重复
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int lo = i + 1, hi = nums.length - 1;
                int sum = 0 - nums[i];

                while (lo < hi) {
                    if (nums[lo] + nums[hi] == sum) {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));

                        // 去重：跳过重复的第二个数
                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;

                        // 去重：跳过重复的第三个数
                        while (lo < hi && nums[hi] == nums[hi - 1]) hi--;

                        lo++;
                        hi--;
                    } else if (nums[lo] + nums[hi] < sum) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }

        return res;
    }
}

代码拆解

这段代码虽然不长，但有几个细节特别重要。 如果这些地方理解不到位，就很容易写出重复答案，或者漏掉某些结果。

1. 为什么排序之后才能做？

Arrays.sort(nums);

排序以后，整个数组变成有序的。

这样当我们固定 nums[i] 后，就可以利用双指针的性质：

• 当前和太小，左指针右移

• 当前和太大，右指针左移

因为数组是有序的，所以这种移动是有方向意义的。

如果数组无序，你就不能确定移动哪边能让和变大或变小，也就没法使用双指针。

另外，排序之后，相同数字会挨在一起，这也为后面的去重创造了条件。

2. 为什么 nums[i] > 0 可以直接结束？

if (nums[i] > 0) break;

因为数组已经排序。

如果当前固定的第一个数都已经大于 0 了，那么后面的数只会更大。 三个正数相加，不可能等于 0。

所以一旦出现这种情况，就不需要继续枚举了，直接退出循环即可。

这一步虽然只是一个小优化，但很常见，也很实用。

3. 为什么要对 i 去重？

if (i == 0 || (i > 0 && nums[i] != nums[i - 1]))

这句代码的作用是：

如果当前的 nums[i] 和前一个数一样，那么这一轮就跳过。

原因很简单。 如果第一个数重复了，那么后面通过双指针找到的三元组，大概率也会重复。

举个例子：

nums = [-1, -1, 0, 1, 2]

当第一个 -1 被固定时，可能找到：

[-1, 0, 1]

如果第二个 -1 再作为起点去找一遍，得到的还是同样的答案。 所以这里必须去重。

4. 为什么找到答案后，还要继续跳过重复值？

while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;

这是整道题最容易漏掉的地方。

当我们已经找到一组满足条件的三元组后，比如：

[-1, 0, 1]

如果左边接下来还是 0，右边接下来还是 1，那么继续移动一步之后，得到的仍然是同样的三元组。

为了避免结果重复，就要把这些相同数字全部跳过去。

也就是说：

• lo 要跳过所有重复的值

• hi 也要跳过所有重复的值

等跳过之后，再继续往中间收缩。

5. 为什么找到答案后要同时 lo++ 和 hi--？

lo++;
hi--;

因为当前这组 (nums[i], nums[lo], nums[hi]) 已经被记录进答案了。

接下来需要继续找新的组合，所以左右指针都要向中间移动。

如果只移动一边，就可能重复使用刚才已经处理过的数字组合。

手动模拟一遍

我们用经典样例来走一遍流程：

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

先排序后得到：

[-4,-1,-1,0,1,2]

第一轮：i = 0

固定：

nums[i] = -4

目标值：

sum = 4

此时：

• lo = 1

• hi = 5

不断尝试后会发现，没有两个数能加起来等于 4。

所以这一轮没有结果。

第二轮：i = 1

固定：

nums[i] = -1

目标值：

sum = 1

此时：

• lo = 2，值为 -1

• hi = 5，值为 2

有：

-1 + 2 = 1

正好等于目标值，所以找到第一组答案：

[-1, -1, 2]

接着继续移动指针。

然后会再次找到：

[-1, 0, 1]

所以这一轮一共得到两组答案。

第三轮：i = 2

当前值仍然是：

nums[i] = -1

但因为它和前一个数相同，所以跳过，不再重复处理。

第四轮：i = 3

固定：

nums[i] = 0

目标值：

sum = 0

此时右边只剩 [1,2]，它们相加不可能等于 0，所以没有新答案。

最终返回：

[[-1,-1,2],[-1,0,1]]

为什么时间复杂度是 O(n^2)？

很多人看到代码里有一个 for，里面又套了一个 while，会下意识怀疑是不是 O(n^3)。

其实不是。

原因在于：

• 外层 for 循环执行 n 次

• 每次固定 i 后，内部双指针 lo 和 hi 只会线性移动，不会回头

也就是说，对于每个 i，双指针最多扫描一遍数组剩余部分。

所以总时间复杂度是：

O(n^2)

这比暴力枚举的 O(n^3) 已经快很多了。

空间复杂度

如果不算返回结果本身，额外空间主要来自排序。

如果按一般题解习惯来写，可以认为额外空间复杂度为：

O(1) ~ O(log n)

具体取决于排序实现。

这道题真正难在哪里？

三数之和这道题真正难的地方，不是双指针本身，而是：

双指针和去重如何正确配合。

很多人第一次写这道题，容易出现下面几类问题：

1. 忘记对 i 去重，导致结果重复

2. 找到答案后没有对 lo 和 hi 去重，导致结果集中出现相同三元组

3. 指针移动顺序写错，导致漏解

4. 没有先排序，结果双指针逻辑根本跑不通

所以这道题最重要的不是背代码，而是理解整个流程：

• 先排序

• 枚举第一个数

• 把后两数之和转成双指针问题

• 在每个关键位置做去重处理

只要这几个步骤想清楚，代码自然就能写出来。

总结

这道题是一道非常经典的“排序 + 双指针 + 去重”题目。

它的核心思路可以概括成下面几步：

1. 先对数组排序

2. 依次固定第一个数 nums[i]

3. 在后面的区间中用双指针寻找两个数，使它们的和等于 -nums[i]

4. 在固定第一个数、找到答案之后，都要注意去重

5. 最终得到所有不重复的三元组

所以，这道题虽然是中等题，但其实非常锻炼基本功。 因为它不仅考察双指针，还考察你对“去重”这种细节处理的掌握程度。

如果你把这道题真正吃透，那么后面再遇到：

• 四数之和

• 最接近的三数之和

• 有序数组中的两数之和

这些题目时，思路都会顺很多。

三数之和本质上就是这样一种非常典型的模板题。 值得反复练，直到你能不看题解自己把“排序 + 双指针 + 去重”完整写出来为止。