LeetCode LCR 007. 三数之和
目录
题目描述
题意分析
给一个整数数组
nums，找出所有满足 $a + b + c = 0$ 的三元组，要求返回的结果中不能包含重复的三元组。三个数必须来自不同的下标，但数值本身可以相同。「返回所有解」而不是「返回是否存在」或「返回个数」，说明必须真的把每个三元组构造出来，输出规模本身就可能达到 $O(n^2)$ 量级，因此时间复杂度的下界就在 $O(n^2)$ 附近——这直接告诉我们 $O(n^3)$ 的三重枚举是要被优化掉的，而 $O(n^2)$ 是可以接受的目标。
「不能有重复三元组」是本题真正的难点，也是它比两数之和难得多的原因。重复来源有两种：一是同一个三元组以不同的下标组合被找到多次（比如数组里有两个
-1），二是同一个三元组以不同的顺序被输出。第二种可以靠「规定三元组内部有序」消除，而这恰好提示了先排序——排序既让顺序唯一化，又为后续利用单调性做好铺垫。数据规模是 $n \le 3000$，$O(n^2)$ 约 $10^7$，完全能过；$O(n^3)$ 约 $2.7 \times 10^{10}$，必然超时。元素取值范围是 $[-10^5, 10^5]$，三数之和最大约 $3 \times 10^5$，不会溢出 32 位。
边界方面：数组长度可能小于 $3$，此时无解；数组可能全是 $0$（答案只有一个
[0,0,0]），也可能全是正数或全是负数（无解）。这些情况都应该被主逻辑自然覆盖，不该靠特判堆砌。
解法：双指针收缩边界
核心思路
暴力做法是三重循环枚举下标 $i < j < k$，判断和是否为 $0$，再用哈希集合对结果去重。$O(n^3)$ 时间，而且去重要靠对每个三元组排序后转字符串，常数极大。瓶颈在最内层：固定了
i和j之后，我们其实只是在问「有没有值等于 $-(nums[i] + nums[j])$」，用线性扫描回答太浪费。突破口是先把数组排好序。排序带来两个红利：其一，三元组内部天然按非递减排列，「同一组数的不同顺序」这类重复被彻底消灭；其二，数组变得单调，可以用相向双指针在 $O(n)$ 内把「固定一个数、在剩下区间里找和为定值的一对」解决掉，从而把总复杂度压到 $O(n^2)$。
固定最小的那个数
nums[i]后，问题变成在有序区间 $[i+1, n-1]$ 上找两数之和等于 $-nums[i]$。令j指向区间左端、k指向右端，令 $x = nums[i] + nums[j] + nums[k]$：若 $x < 0$，说明和偏小。此时
nums[k]已经是区间内最大的可选值，j与任何比k更小的下标配对只会让和更小，所以下标j上的全部配对都可以整体排除，j右移。若 $x > 0$ 同理，k左移。若 $x = 0$，记录答案，然后两端同时收缩。这就是双指针每一步能安全丢掉一整行/一整列的依据，也是它优于二分的地方。要维持的不变量是：所有以
nums[i]为最小元素、且尚未被检查的合法配对，其两个下标都落在区间 $[j, k]$ 内。每次移动指针都伴随着一次「这一侧的所有配对都不可能成立」的论证，不变量才不会被破坏。去重则分三处独立处理：
i层跳过与前一个相同的值；命中答案后j向右跳过与刚用过的值相同的元素、k向左跳过与刚用过的值相同的元素。三处都必须有，缺一个就会漏掉某种重复形态。
解题步骤
- 先
sort排序。这是后面所有推理的地基：没有序就没有单调性，双指针的收缩依据不成立，去重也无从下手。- 外层枚举最小元素的下标
i，上界是n - 2（写成i < n - 2），因为后面至少要留两个位置给j和k。这个上界同时让长度小于 $3$ 的数组一次循环都不进，无需特判。- 外层附加剪枝
nums[i] <= 0。排序后nums[i]是三元组里最小的数，若它已经大于 $0$，三个数之和必然为正，后面全部无解，可以直接停。i层去重：if (i > 0 && nums[i] == nums[i - 1]) continue;。判断的是「和前一个相同」而不是「和后一个相同」——后者会把[-1, -1, 2]这种需要用到两个相同值的答案整个跳过。- 双指针初始化
j = i + 1、k = n - 1，条件j < k。用严格小于保证三个下标互不相同。- 按三数之和的符号收缩：小于 $0$ 时
++j（放弃当前j的所有配对），大于 $0$ 时--k，等于 $0$ 时记录答案。- 命中后两端同时收缩：只动一端必然导致下一轮的和不为 $0$（另一端固定时和是严格单调的），白白浪费一轮；同时动两端才能继续搜索新的解。
- 命中后再跳过重复值：
while (j < k && nums[j] == nums[j - 1]) ++j;和while (j < k && nums[k] == nums[k + 1]) --k;。比较的对象是「刚刚用过的那个值」，所以下标要看j - 1和k + 1。- 循环结束返回收集到的答案。
以
nums = [-1, 0, 1, 2, -1, -4]走一遍。排序后是[-4, -1, -1, 0, 1, 2]，n = 6。i = 0（值 $-4$，满足 $\le 0$）：j = 1, k = 5，和为 $-4-1+2=-3<0$，j = 2；和为 $-4-1+2=-3<0$，j = 3；和为 $-4+0+2=-2<0$，j = 4；和为 $-4+1+2=-1<0$，j = 5，此时j < k不成立，本轮结束。i = 1（值 $-1$，与nums[0] = -4不同，不跳过）：j = 2, k = 5，和为 $-1-1+2=0$，记录[-1, -1, 2]，两端同时收缩成j = 3, k = 4；跳重检查——nums[3] = 0 ≠ nums[2] = -1，nums[4] = 1 ≠ nums[5] = 2，都不跳；和为 $-1+0+1=0$，记录[-1, 0, 1]，收缩成j = 4, k = 3，j < k不成立，本轮结束。i = 2（值 $-1$，与nums[1]相同）：直接continue——正是这一步挡住了[-1, 0, 1]被第二次找到。i = 3（值 $0$）：j = 4, k = 5，和为 $0+1+2=3>0$，k = 4，循环结束。i = 4时i < n - 2不成立，整体结束。最终答案[[-1, -1, 2], [-1, 0, 1]]。
代码实现
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序是全部推理的地基：既统一了三元组内部顺序，又提供了单调性。
Arrays.sort(nums);
List<List<Integer>> answer = new ArrayList<>();
int n = nums.length;
// nums[i] 是三元组里最小的数，一旦为正后面必然无解。
for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
// 与前一个值相同则跳过，避免以同一个最小值重复搜索。
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1, k = n - 1;
while (j < k) {
int x = nums[i] + nums[j] + nums[k];
if (x < 0) {
++j;
} else if (x > 0) {
--k;
} else {
answer.add(List.of(nums[i], nums[j++], nums[k--]));
// 跳过与刚用过的值相同的元素，两侧都要跳。
while (j < k && nums[j] == nums[j - 1]) {
++j;
}
while (j < k && nums[k] == nums[k + 1]) {
--k;
}
}
}
}
return answer;
}
}
func threeSum(nums []int) (answer [][]int) {
sort.Ints(nums)
n := len(nums)
for i := 0; i < n-2 && nums[i] <= 0; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
j, k := i+1, n-1
for j < k {
x := nums[i] + nums[j] + nums[k]
if x < 0 {
j++
} else if x > 0 {
k--
} else {
answer = append(answer, []int{nums[i], nums[j], nums[k]})
j, k = j+1, k-1
for j < k && nums[j] == nums[j-1] {
j++
}
for j < k && nums[k] == nums[k+1] {
k--
}
}
}
}
return
}
复杂度分析
- 时间复杂度：$O(n^2)$。排序是 $O(n \log n)$，被后面的双层结构盖过；外层枚举 $n$ 个起点，内层的
j与k各自单向移动、合计至多走 $n$ 步，所以每个起点的代价是 $O(n)$。凭的是「有序性让每次指针移动都能排除一整批配对」，而不是逐对检查。- 空间复杂度：$O(\log n)$（不计返回值）。只有排序的递归栈开销，双指针本身只用了
i、j、k、x几个标量；答案列表是题目要求的输出，不计入额外空间。
关键点总结
- 看到「找若干个数使和为定值」且「要输出全部解、需去重」，标准套路就是排序 + 固定前 $k-2$ 个数 + 相向双指针，$k$ 数之和都能套这个模板，复杂度是 $O(n^{k-1})$。
- 双指针能成立的核心论证是「移动一端等于排除一整批配对」，答题时要能把这句话说出来，而不是只描述代码动作。
- 去重要在每个枚举层各做一次，且比较对象都是「上一个已经用过的值」。把去重寄托在最后用
HashSet过滤是能过，但常数大且掩盖了对问题结构的理解。- 命中后必须两端同时收缩：另一端固定时和是严格单调的，只动一端一定不会再命中，属于纯浪费。
i < n - 2这个上界顺带处理了短数组，nums[i] <= 0这个剪枝顺带处理了全正数组——好的循环边界能把特判吸收进主逻辑。- 面试视角：这是最高频的双指针题之一，面试官通常会追问三件事——「怎么保证不重复」「为什么排序后可以用双指针」「能不能做到 $O(n^2)$ 以下」。第三问的标准答案是不能：输出规模本身就可能是 $O(n^2)$，因此 $O(n^2)$ 已是这道题的下界。能主动说出这一点，比写完代码更能体现深度。
易错点总结
- 错误写法：不排序直接用哈希表找第三个数。输入
[-1, 0, 1, 2, -1, -4]会把[-1, 0, 1]以两种下标组合各找一次，返回重复三元组。- 错误写法：
i层去重写成if (nums[i] == nums[i + 1]) continue;。输入[-1, -1, 2]时i = 0被跳过，唯一的答案[-1, -1, 2]直接丢失。- 错误写法：命中后只写
++j不写--k。输入[-1, -1, 0, 1, 2]命中[-1, -1, 2]后k仍停在下标 $4$，紧接着的跳重语句读nums[k + 1]即下标 $5$，直接数组越界。- 错误写法：跳重时比较
nums[j] == nums[j + 1]。输入[-2, 0, 0, 2, 2]时会把还没检查过的元素当成用过的跳掉，漏掉[-2, 0, 2]。- 错误写法：跳重的
while里漏掉j < k的边界。输入[0, 0, 0, 0]时命中后j会一路越过k直至下标越界。- 错误写法：双指针条件写成
j <= k。输入[-2, 1, 3]时k收缩到 $1$ 后j == k == 1，同一个 $1$ 被当成两个元素使用，误报出[-2, 1, 1]，而正确答案是空。- 错误写法：外层剪枝写成
nums[i] < 0（严格小于）。输入[0, 0, 0]时nums[0] = 0不满足条件，循环一次都不进，返回空列表而不是[[0, 0, 0]]。- 错误写法：用
List收集后调用new ArrayList<>(new HashSet<>(answer))去重。可以过，但每个三元组都要算哈希、比较列表，常数放大数倍，而且掩盖了真正的去重逻辑，面试中会被追问「不用集合怎么做」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 15. 三数之和 | 中等 | 与本题同题，可直接套用同一份排序 + 双指针 + 三处去重 |
| 18. 四数之和 | 中等 | 多固定一个数变成两层枚举，且四数之和可能溢出，需用 long
|
| 16. 最接近的三数之和 | 中等 | 无需去重，改为在每次移动时更新与目标的最小差值 |
| 259. 较小的三数之和 | 中等 | 只统计个数，命中不等式时可一次性加上 k - j 个方案 |
| 611. 有效三角形的个数 | 中等 | 固定最大边并让双指针同向收缩，判定条件是两小边之和大于最大边 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 本题内层的最小版本，输入已有序，无需排序也无需去重 |
| LCR 006. 两数之和 II - 输入有序数组 | 简单 | 与 167 同题但下标 0-based，可用来单练相向双指针的收缩依据 |
| 面试题 16.24. 数对和 | 中等 | 同为排序后配对，但要求输出全部数对且每个元素只能用一次 |