刷题刷到 LeetCode 15 题“三数之和”，这个位置非常微妙。前十几题基本是数组、字符串、动态规划热身，而这一题一出来，很多人的思维会卡住。题目本身不复杂：给定一个整数数组，找出所有和为 0 且不重复的三元组。但“不重复”三个字是真正的杀手，它逼着你从“能不能做出来”跨到“怎么做才能又快又对”。作为经典中的经典，这道题集中考察了排序预处理、双指针收缩、哈希去重思路，以及最重要的——写代码时的边界感。无论你是刚开始准备面试，还是已经刷了一百题想补漏，三数之和都是一道必须吃透的题。
我当年第一次做这题时，第一反应是三重循环暴力解，当场被时间复杂度教做人。后来学乖了，老老实实排序加双指针，才体会到什么叫“原来思路是这么顺的”。这篇总结我会把从暴力到双指针的完整思考过程、去重细节、常见错误、代码实现以及扩展题型全部聊透，保证你读完能直接上手写，也能应付面试官的追问。
1. 先看清问题本质：三数之和到底在考什么
1.1 题目描述与原题拆解
题目给的是一个整数数组nums，要求返回所有满足nums[i] + nums[j] + nums[k] == 0的三元组，并且三元组之间不能重复。注意几个容易忽略的条件：
- 同一个元素不能重复使用，也就是说
i、j、k是三个不同的下标。 - 三元组内部顺序无关紧要，
[-1,0,1]和[1,-1,0]被视为同一个三元组。 - 结果中不能包含重复三元组，比如数组里有两个
-1，只能输出一个[-1,0,1]。
这类问题最让人头疼的就是去重，因为如果只要求找到任意一组，三重循环或者哈希直接就出来了。难就难在“所有”和“不重复”这两个词上。
原题举例：nums = [-1,0,1,2,-1,-4]，正确结果是[[-1,-1,2],[-1,0,1]]。注意[-1,0,1]出现了两次吗？并没有。因为数组里有两个-1，但题目只允许输出一个三元组，这里就暗含了去重逻辑：你要跳过重复元素，而不是把重复组合都塞进结果。
题目本身的核心逻辑其实是在做“组合枚举”，要求你枚举所有三元素组合，但组合之间不能有重复。简单粗暴的组合枚举是 C(n,3) 种可能，n 一旦到几百，三重循环就废了。
1.2 为什么这题是面试高频题
三数之和在面试题里出现频率极高，原因有三个。
第一，它有一个非常清晰的最优解法——排序加双指针，这属于基础算法里“预处理 + 相向双指针”的经典套路。面试官希望看你能不能想到先排序，能不能把 O(n³) 降到 O(n²)。
第二，去重逻辑设计考察的是代码细节。很多候选人能写出双指针主体，但去重条件写错，导致结果里有一堆重复三元组。这个问题能瞬间拉开代码能力差异。
第三，这题可以自然衍生出很多变体：最接近的三数之和、四数之和、删除重复元素后的组合数等等。会了这道题，后面的四数基本是复制粘贴再加一层循环。面试官可以用一道题考察好几个层级的水平，性价比极高。
所以，与其说这道题在考“你会不会双指针”，不如说它是在考“你能不能把简单的东西写严谨”。
2. 从暴力解到双指针：完整思维演进
2.1 最直观的暴力三重循环
看到三数之和，第一反应自然是三重循环。直接写的话，长这样：
def threeSum(nums): n = len(nums) res = [] seen = set() for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): if nums[i] + nums[j] + nums[k] == 0: triplet = tuple(sorted([nums[i], nums[j], nums[k]])) if triplet not in seen: seen.add(triplet) res.append(list(triplet)) return res这个版本能保证结果不重复，因为每个三元组排序后转元组放进 set。但问题太明显：时间复杂度是 O(n³)，空间复杂度也用了 O(n) 的 set。当 n=3000，直接超时。
暴力解的意义在于帮你理解问题本身，而不是作为最终方案。你可以仔细想想，暴力解里哪些计算是重复的。三个数求和，内层循环做了大量的无用功，因为后两个数的组合根本不需要全量枚举。我们能不能固定一个数，然后去找另外两个数？这就是优化的起点。
2.2 借助哈希表优化到两重循环
固定一个数 i，问题变成在剩下的元素中找两数之和等于target - nums[i]。这里有两个思路：一个是两重循环加哈希表，另一个是排序后双指针。
先用两重循环加哈希表举个例子：
def threeSum(nums): n = len(nums) res_set = set() for i in range(n): target = -nums[i] table = {} for j in range(i + 1, n): need = target - nums[j] if need in table: triplet = tuple(sorted([nums[i], nums[j], need])) res_set.add(triplet) table[nums[j]] = j return [list(t) for t in res_set]这是把“两数之和”那张哈希表搬过来用。时间复杂度降到 O(n²)，但有两个问题：
- 结果去重还得靠最后排序 + set，因为同一个三元组可能被不同位置的 i 枚举到。
- 空间复杂度 O(n)，因为每次循环都建一张哈希表。
哈希表方案其实是可行的，但面试官大概率会让你继续优化，因为它在“去重”这件事上处理得很笨重，而且如果数组是排好序的，你还有更优雅的做法。
2.3 排序加双指针的经典解法
双指针解法的思路是：
- 先将数组排序。
- 固定最左边的下标 i，作为第一个数。
- 然后用两个指针 left 和 right 分别指向 i 后面区间的两端。
- 计算三数之和
s = nums[i] + nums[left] + nums[right]。 - 如果
s == 0，记录结果，然后移动左右指针并去重。 - 如果
s < 0，说明左侧数太小，left += 1。 - 如果
s > 0，说明右侧数太大，right -= 1。
为什么排序有用？因为排序后数组有序，两个指针才能根据和的大小进行“向左或向右”的调节。想象你有一根升序排列的刻度尺，一个指针从头走，一个指针从尾走，如果和太小，就把左指针右移放大；如果和太大，就把右指针左移缩小。这个过程非常像二分查找的“折中”思想，但它是同时调节两个端点。
这里有个关键推论：当第一个数固定时，剩余部分找两数之和等于固定值的问题，就能用双指针在线性时间内解决。整体复杂度就变成了最外层 O(n) 乘以内层双指针 O(n)，总 O(n²)。
去重具体怎么写，是这项技术最大的坑，我单独用一节来讲。
3. 实操细节：去重、边界与代码实现
3.1 排序数组与指针移动的边界
先说一下排序后的边界。外层循环从i=0遍历到len(nums)-3就够了，因为至少还要留两个位置给 left 和 right。当然，你写成range(n)也不会越界，只要内部判断提前退出就行。但更严谨的写法是：
for i in range(len(nums) - 2): # ...为什么是len(nums) - 2？因为 i 是三元组的最小元素（在有序数组里），如果 i 已经走到了倒数第三个元素之后，后面没有足够的位置放 left 和 right 了。
还有一个极其重要的剪枝：
if nums[i] > 0: break因为数组已经有序，如果最小的 nums[i] 已经大于 0，那么后面任何两个数都比它大，三数之和必然大于 0，直接退出循环。同样，if nums[i] + nums[left] + nums[right] < 0就左指针右移，注意左指针增加后要继续跳过重复值。
指针移动时的边界条件要特别注意：while left < right这个条件必须始终成立，否则左右指针可能交叉。一旦交叉，说明区间内已经没有元素可用了，必须停止内层循环。在记录合法结果后，左右指针都需要移动，但移动时一定要跳过所有与当前值重复的元素，否则会产生相同三元组。
3.2 去重的完整逻辑
去重是整个题目的灵魂。很多网上的题解喜欢把去重写在两个地方：外层 i 的去重，以及内层 left/right 的去重。
先看外层 i 的去重：
if i > 0 and nums[i] == nums[i-1]: continue这行代码的含义是：如果当前这个数的值和上一个数相同，那么当前这轮循环得到的所有三元组，在上一轮一定已经全部被找过了。为什么这么肯定？因为排序后，相同值一定连续出现。固定 nums[i-1] 时，它在数组后面的区间中找两个数与它匹配；固定 nums[i] 时，剩下的区间比上一轮更小，但之前的组合已经包含了所有可能，所以直接跳过是最安全、最优的写法。
有人会问：如果写成if i < n-1 and nums[i] == nums[i+1]: continue行不行？不行。因为你提前跳过了当前值，但当前值作为三元组的第一个数，它可能和后面的数组合出新的结果。举例：[-1,-1,0,1]，i=0 的-1和 i=1 的-1值相同。如果看到“下一个元素相同”就跳过 i=1，那 i=1 这个位置就永远作为首元素参与不了外部循环，但事实上它自己并不需要作为首元素，因为 i=0 已经处理过所有包含一个-1的三元组，包括[-1,0,1]。这个例子里跳过 i=1 看起来没问题，但换成更复杂的情况，skip next会导致漏解。所以正确的观念就是：每个值第一次出现时，必须完整处理一轮；之后遇到相同值，直接跳过。
再看向内层 left/right 的去重。当找到一个三元组满足条件后，写法是：
ans.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1为什么要这两个 while？因为如果不跳过，比如[-2,0,0,2,2]中，i=0 固定-2，left 在第一个 0，right 在最后一个 2，记录[-2,0,2]。然后如果不跳过，left 右移一位还是 0，right 左移一位还是 2，又会记录相同的三元组，产生重复。所以必须在记录后，将 left 和 right 移动到与当前值不同的新位置，再分别往中间走一步。
这里有个容易犯的错误：只在 while 里跳过，但跳过之后忘了left += 1和right -= 1，导致指针还是指向重复元素。务必记住，while 循环跳的是“连续重复区间”，跳完后还需要正常移动一步。
另一个常见疑问：在s == 0之前，也就是指针还没找到正确答案时，要不要去重？不需要。因为只要s != 0，左右指针的移动方向是确定的，不会产生重复结果。重复只会从“记录成功”的那一刻开始出现。
3.3 Python 实现与核心注释
直接给出可运行的标准解法。
def threeSum(nums): nums.sort() n = len(nums) res = [] for i in range(n - 2): # 剪枝：第一个数大于0，后面的数更大，不可能有解 if nums[i] > 0: break # 去重：外层相同值只处理一次 if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, n - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s < 0: left += 1 elif s > 0: right -= 1 else: res.append([nums[i], nums[left], nums[right]]) # 去重并移动指针 while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return res这段代码里，nums.sort()属于就地排序，会改变原数组。面试时如果面试官要求不能修改原数组，可以先用sorted(nums)复制一份再排序，代价是 O(n) 的空间。多数情况下，LeetCode 允许原地排序，所以直接用没问题。
关于 Python 的语法，注意nums[left] == nums[left + 1]中left + 1不要越界，但 while 条件里已经先做了left < right判断，所以 safe。同理nums[right - 1]也有left < right保护。
让我们手动跑一遍示例：nums = [-1,0,1,2,-1,-4]，排序后变成[-4,-1,-1,0,1,2]。
- i=0，nums[0] = -4。left=1，right=5，三数和为 -4 + (-1) + 2 = -3 < 0，left=2。再算 -4 + (-1) + 2 = -3，left=3。算 -4+0+2=-2，left=4；-4+1+2=-1；left=5 后结束。
- i=1，nums[1] = -1。由于 i>0 且 nums[1]==nums[0]，跳过。
- i=2，nums[2] = -1。同样跳过。
- i=3，nums[3]=0。left=4，right=5，和为0+1+2=3 >0，right=4，循环结束。
- i=4，n-2? i range(4) 实际到3结束，所以 i=4 不会执行。
注意到最终结果里没有包含[-4,2,2]?不存在。结果是[[-1,-1,2],[-1,0,1]]。验证正确。
4. 易错点与常见问题排查
4.1 典型错误一：结果包含重复三元组
这个错误几乎每个人都犯过。比如写成这样：
if s == 0: res.append([nums[i], nums[left], nums[right]]) left += 1 right -= 1而不做任何去重。对于输入[-2,0,0,2,2]，i=0 固定 -2，left 指向 index1 的 0，right 指向 index4 的 2，记录[-2,0,2]；然后 left+1 指向 index2 的 0，right-1 指向 index3 的 2，再次满足和为 0，又记录[-2,0,2]。最终返回[[-2,0,2],[-2,0,2]]，这就是重复。
修复方法就是前面说的：在记录后，用两个 while 把 left 和 right 移动到无重复区域。另外，外层 i 的去重也不能少，否则当数组有多个相同首元素时也会重复。
4.2 典型错误二：指针越过边界
有人会在while left < right内部不小心写错指针移动顺序，比如在去重 while 之后再移动时，没重新检查left < right。严格来说，只要你的去重 while 都带了left < right条件，随后移动 one step 其实也有越界风险？比如 left 已经到 n-1 了，再去执行 left += 1 就变成 n。不过下一轮 while 判断会退出，不会访问越界元素，所以不会产生运行时错误。但如果你在去重 while 之后继续使用nums[left]，就可能 IndexError。
还有人在外层循环中写for i in range(n)而不是range(n-2)，然后在循环里left, right = i+1, n-1，当 i=n-2 或 n-1 时，虽然可能因为left >= right直接跳过，但容易让人困惑。更稳妥的做法是写成range(n-2)，明确表示 i 最多到倒数第三个位置。
4.3 性能对比总结
为了让你直观感受复杂度差异，我列个表格：
| 方法 | 时间复杂度 | 空间复杂度 | 适用规模 |
|---|---|---|---|
| 暴力三重循环 | O(n³) | O(1) 或 O(n)（取决于去重方式） | n < 100 |
| 哈希表辅助 | O(n²) | O(n) | n < 1000 |
| 排序 + 双指针 | O(n log n + n²) = O(n²) | O(log n) 到 O(n)（取决于排序空间） | n < 5000 没问题 |
注意排序本身是 O(n log n)，但 n² 项主导，所以整体是 O(n²)。双指针方案的空间复杂度主要来自排序，Python 的 Timsort 通常需要 O(n) 额外空间，但多数面试讨论中我们只看额外辅助空间，如果不算排序，双指针本身只用 O(1) 空间。这也是它优于哈希表方案的一个点。
实测 LeetCode 上，nums长度达到 3000 时，双指针解法用时约几十毫秒，哈希表方案可能慢一两倍，而且代码更难去重。所以面试时推荐直接写双指针。
5. 扩展思考与个人经验
5.1 变形题：最接近的三数之和
LeetCode 16 题“最接近的三数之和”几乎是同一套代码，只改一点点。题目要求返回与target最接近的三数之和。解法还是排序加双指针，但在每次计算s时，用一个变量记录diff = abs(s - target)，如果diff小于当前最小差，就更新答案。然后根据s与target的大小关系移动指针。去重逻辑甚至可以省略，因为只返回一个数，不要求列出所有组合。
如果你能熟练写出三数之和的骨架，16 题就等于白送分。我建议你写三数之和时，顺便用多一个参数去实现“小于等于 target 的最大和”之类的功能，这样面试变形题也能游刃有余。
5.2 环形链式思路：nSum 原则
三数之和再往上扩展，就是四数之和、五数之和。LeetCode 18 题“四数之和”要求固定两个数，剩下两数用双指针。代码逻辑是在三数之和的外面再套一层循环：
for i in range(n - 3): if nums[i] > target and target > 0: break if i > 0 and nums[i] == nums[i-1]: continue for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j-1]: continue left, right = j + 1, n - 1 # 双指针逻辑你会发现，nSum 问题的套路就是：递归或者嵌套循环固定前 n-2 个元素，最后两个元素用双指针找。这就是很多算法模板里的 nSum 思想。理解了三数之和，四数之后只是重复劳动。
我在实际刷题时总结了一个小技巧：写 nSum 时，把递归的参数设计成sums(nums, target, count, start, path)，用递归逼近 base casecount == 2，然后双指针查两数之和。这种方式虽然代码量多一点，但可以一次性解决 2Sum、3Sum、4Sum，甚至多到 5Sum。不过面试时不要一上来就写递归，先用最直接的迭代更不容易出错。
5.3 面试时如何分析和作答
面试官如果让你做三数之和，一定要先说思路，而不是直接沉默着写代码。我建议你按下面这个模板组织语言：
第一，确定暴力解：三重循环枚举，O(n³)，然后说能不能优化。第二，观察到如果数组有序，固定一个数后，剩余两数可以用双指针，因为有序性保证了移动指针的正确性。第三，说明复杂度降到 O(n²)，同时详细介绍去重策略。第四，手写代码时，注意剪枝条件nums[i] > 0和越界判断。
面试官常会追问几个问题，比如“为什么排序后不会丢解？”你要解释：排序只改变元素顺序，不改变组合的存在性；双指针枚举的是所有 i、left、right 的有效组合，不会漏掉任意一个和为 0 的三元组。再比如“如果数组中有很多重复元素，会不会有性能问题？”你要答：重复元素通过 while 跳过，每个重复元素只会被指针扫过一次，整体依然 O(n²)，不会退化。
我个人在实际操作中还发现，很多人手写代码时把right的初始值写成n而不是n-1，导致越界。这种低级错误非常冤枉。只要记住：数组索引从 0 开始，最后一个元素是n-1，内层循环才能 run。
另外想提醒一点：题解帖子里的“去重”代码五花八门，有些写法在理论上对，但可读性差。比如有人写成while left < right and nums[left] == nums[left+1]: left+=1之后没有额外left+=1，而是把 while 的条件改成nums[left] == nums[left-1]，看着很绕。我建议你固定一个模式：先跳过重复，再统一 +1，这样不容易乱。
说到底，三数之和值得你反复手写三次：第一次照着题解抄，第二次合上书自己写，第三次限时 15 分钟从零开始。三次之后，这类双指针问题基本就能形成肌肉记忆了。
最后分享一个刷题习惯：每写完一道题，我会在代码注释里补充一行“这题犯了什么错”。比如三数之和这一题，我当时的注释是“去重必须在记录后，不能在记录前”。等你刷到 100 题时，回头看这些注释，就是最宝贵的错题本。
