刷题刷到 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。当 n3000直接超时。暴力解的意义在于帮你理解问题本身而不是作为最终方案。你可以仔细想想暴力解里哪些计算是重复的。三个数求和内层循环做了大量的无用功因为后两个数的组合根本不需要全量枚举。我们能不能固定一个数然后去找另外两个数这就是优化的起点。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 排序数组与指针移动的边界先说一下排序后的边界。外层循环从i0遍历到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[i1]: continue行不行不行。因为你提前跳过了当前值但当前值作为三元组的第一个数它可能和后面的数组合出新的结果。举例[-1,-1,0,1]i0 的-1和 i1 的-1值相同。如果看到“下一个元素相同”就跳过 i1那 i1 这个位置就永远作为首元素参与不了外部循环但事实上它自己并不需要作为首元素因为 i0 已经处理过所有包含一个-1的三元组包括[-1,0,1]。这个例子里跳过 i1 看起来没问题但换成更复杂的情况skip next会导致漏解。所以正确的观念就是每个值第一次出现时必须完整处理一轮之后遇到相同值直接跳过。再看向内层 left/right 的去重。当找到一个三元组满足条件后写法是ans.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1为什么要这两个 while因为如果不跳过比如[-2,0,0,2,2]中i0 固定-2left 在第一个 0right 在最后一个 2记录[-2,0,2]。然后如果不跳过left 右移一位还是 0right 左移一位还是 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]。i0nums[0] -4。left1right5三数和为 -4 (-1) 2 -3 0left2。再算 -4 (-1) 2 -3left3。算 -402-2left4-412-1left5 后结束。i1nums[1] -1。由于 i0 且 nums[1]nums[0]跳过。i2nums[2] -1。同样跳过。i3nums[3]0。left4right5和为0123 0right4循环结束。i4n-2? i range(4) 实际到3结束所以 i4 不会执行。注意到最终结果里没有包含[-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]i0 固定 -2left 指向 index1 的 0right 指向 index4 的 2记录[-2,0,2]然后 left1 指向 index2 的 0right-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 i1, n-1当 in-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[left1]: left1之后没有额外left1而是把 while 的条件改成nums[left] nums[left-1]看着很绕。我建议你固定一个模式先跳过重复再统一 1这样不容易乱。说到底三数之和值得你反复手写三次第一次照着题解抄第二次合上书自己写第三次限时 15 分钟从零开始。三次之后这类双指针问题基本就能形成肌肉记忆了。最后分享一个刷题习惯每写完一道题我会在代码注释里补充一行“这题犯了什么错”。比如三数之和这一题我当时的注释是“去重必须在记录后不能在记录前”。等你刷到 100 题时回头看这些注释就是最宝贵的错题本。