LeetCode 15. 三数之和绝对是我刷题笔记里的“钉子户”。它稳稳站在 LeetCode 热门 100 题的前排每次周赛评论区里都有老哥拿它当双指针模板聊我在好几场面试里也遇到它不是作为开场题而是作为“你来解释一下这个去重逻辑”的引子。这也是我刷题系列笔记的第六篇正好轮到这道题。今天这篇题解我想把三数之和从暴力到双指针、从会写到不踩坑完整拆一遍。适合刚开始刷 LeetCode 的新手也适合那些答案背得滚瓜烂熟、但一被追问就露怯的老手。1. 题目理解与思路演进1.1 先别急着写代码把题意抠清楚三数之和的题干很简短给定一个整数数组 nums找出所有由三个下标 i、j、k 组成的三元组满足三个下标互不相同且 nums[i] nums[j] nums[k] 0返回所有不重复的三元组。这句话里有几个容易被忽略的点。第一个是“三元组不重复”意思是值组合不重复不是下标不重复。比如 [-1, 0, 1] 和 [0, 1, -1] 在数学上都是同一组数字只能保留一个。第二个是输出的是具体数字不是下标所以我们可以大胆排序排序不会影响要返回的值。第三个是数组长度可能小于 3这种直接返回空数组。第四个是数组里可以有重复数字比如 [0, 0, 0] 是一个合法答案不能因为“重复”就把三个 0 也去掉。很多人栽就栽在“重复”两个字上。题目给的示例是 nums [-1, 0, 1, 2, -1, -4]输出是 [[-1, -1, 2], [-1, 0, 1]]。注意里面的 -1 出现了两次两个合法三元组都用到了 -1但它们不是同一个三元组。理解到这个层面才知道去重不是简单地把所有重复元素删掉而是要在枚举过程中避免产生相同的三元组组合。1.2 暴力解不是不能写是写完就知道为什么 TLE最直观的解法是三重循环枚举 i j k判断三个数和是否为 0。这个解法在数组长度很小的时候没问题但 LeetCode 的测试数据动辄几千个元素O(n^3) 的复杂度在 n 3000 时就要跑 270 亿次基本操作提交上去必然是 Time Limit Exceeded。不过面试的时候我建议你先讲暴力解法。它有两个作用第一用最直接的方式向面试官确认“我理解了题意”第二从暴力解的缺陷引出优化方向。暴力解真正的问题不只是慢还在于就算加一个 set 去重三重循环里仍然会反复扫描大量无效组合。比如数组全 0 的时候任何三个 0 都能组成答案暴力解会枚举 C(n,3) 次去重集合里却只有一个 [0, 0, 0]。这种“计算了很多结果但最终都被过滤掉”的浪费在数据规模变大以后非常致命。所以这道题的本质不是“能不能找到”而是“如何高效地找到全部组合同时不做多余计算”。顺着这个思路下一步自然会想能不能把三数之和降维成两数之和1.3 从两数之和迁移过来思路顺很多做过 LeetCode 1. 两数之和的老哥都知道找两个数和为 target 的经典做法是哈希表遍历数组每遇到一个数就查 target - 当前数是否在前面出现过。三数之和可以看作“先固定一个数再在剩下的范围里找两数之和等于它的相反数”。这就是降维。但这里有两个坑。两数之和只要求返回一组解而且返回的是下标所以哈希表很好用三数之和要求返回全部解并且去掉重复值组合这时候哈希表的去重就会变得非常麻烦。另一个坑是如果固定第一个数 a剩下的数组里可能有多组 b c -a你需要全部找出来不能像两数之和原题那样找到一个就 return。想清楚这一层以后你会发现排序几乎是一个必然选择。排序以后重复元素会连在一起去重可以通过“跳过相邻重复值”完成同时有序数组让双指针有了用武之地左指针和右指针可以根据当前和的大小灵活调整不用再借助哈希表额外存储。这也是 LeetCode 社区里绝大多数高赞题解采用“排序 双指针”的原因。2. 排序加双指针核心解法拆到骨头里2.1 为什么第一件事是排序“先排序”这个动作很多人不理解觉得排序会改变元素位置万一题目要求返回下标怎么办还好三数之和只要求返回值所以我们可以放心排序。排序带来两个关键收益。第一去重变得简单。数组有序以后相同的值一定排在一起我们只要在遍历时跳过和前一个位置相同的值就能从源头上避免产生值重复的三元组。第二双指针扫描依赖有序性。假设数组升序排列左指针指向当前范围的最小值右指针指向最大值。三数和偏大时说明需要更小的数只能把右指针往左移动三数和偏小时说明需要更大的数只能把左指针往右移动。每一步移动都有明确的逻辑依据这就是双指针比暴力枚举“聪明”的地方。排序本身的成本是 O(n log n)相对后续 O(n^2) 的双指针扫描来说是可以接受的。空间上JavaScript 或 Python 的排序通常需要 O(log n) 的递归栈空间但比起哈希表方案额外维护一个 set 还是省得多。这道题后续的所有优化几乎都建立在“数组已经有序”这个前提上。2.2 双指针怎么扫才不会漏解双指针的具体流程是这样的外层循环固定第一个数 nums[i]内层用 left 和 right 两个指针分别指向 i1 和 n-1然后让 left 和 right 在 (i, n) 这个区间相向而行。每次计算 sum nums[i] nums[left] nums[right]。如果 sum 小于 0说明三个数整体偏小需要把 left 右移让 nums[left] 变大如果 sum 大于 0说明偏大需要把 right 左移让 nums[right] 变小。如果 sum 恰好等于 0就记录这个三元组然后 left 和 right 同时向中间移动再跳过所有重复值继续找下一组。外层循环的终止条件也很重要。因为至少要留两个位置给 left 和 right所以 i 最大只能到 n - 3也就是range(n - 2)。有些初学者写成range(n)运行起来会导致 left 或 right 越界。另外排序以后如果 nums[i] 已经大于 0那么后面的数都比它大三数和无论如何都不可能等于 0直接 break 退出整个循环。这是一个很实用的剪枝。这里有一个容易想不通的点为什么 sum 等于 0 时left 和 right 要同时移动而不是只移动一个因为如果只把 left 右移sum 会变大不可能再等于 0只把 right 左移同理。所以找到一组解以后两个指针都必须动否则要么死循环要么产生重复结果。2.3 去重逻辑才是这道题的灵魂三数之和的代码模板背下来不难但 99% 的 bug 都出在去重。第一个去重位置是外层循环当 nums[i] 和 nums[i-1] 相等时直接跳过这一轮。注意这里必须比较 nums[i] 和 nums[i-1]而不是 nums[i] 和 nums[i1]。这个区别非常关键。拿 [-1, -1, 2] 举例数组排序后就是 [-1, -1, 2]。如果写成if nums[i] nums[i1]: continue当 i 0 时nums[0] nums[1] 为真直接跳过结果就是漏掉了 [-1, -1, 2] 这个合法答案。正确的写法是“当前这个值和上一个值相同就跳过”因为上一个值已经作为第一个数完成过一轮完整的双指针扫描了再用同样的值做第一个数找出来的三元组必然和上一轮重复。第二个去重位置在内层找到一个 sum 0 的组合后left 向右移动、right 向左移动然后分别跳过和移动前位置值相同的元素。举例说明数组 [-2, 0, 0, 2, 2]找到 [-2, 0, 2] 后left 从 0 移到下一个 0right 从 2 移到下一个 2如果不跳过会再次得到 [-2, 0, 2]被当成新答案加入结果实际上它是重复的。去重的本质是同一轮双指针里同一个值只能作为 left 或 right 使用一次。理解了这一点你在写代码的时候就不会把去重条件放错位置了。3. 完整实现与现场排错3.1 Python 参考实现注释直接抄直接放一版我能稳定写对的 Python 实现注释写得稍微啰嗦一点方便对着检查。def threeSum(nums): nums.sort() n len(nums) ans [] if n 3: return ans for i in range(n - 2): # 剪枝排序后当前数大于 0后面不可能凑出和为 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: total nums[i] nums[left] nums[right] if total 0: left 1 elif total 0: right - 1 else: ans.append([nums[i], nums[left], nums[right]]) # 找到一组后指针同时收缩 left 1 right - 1 # 内层去重跳过和上一个位置相同的值 while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 return ans代码里的细节我一项项说。nums.sort()之后数组长度小于 3 直接返回空这是一个必须有的前置判断。外层 for 循环的结束位置是n - 2因为 i 占据一个位置left 至少是 i 1right 至少是 i 2所以 i 最大到 n - 3。内层 while 的判断条件是left right两指针相遇时停止。如果你用的是 C 或 Java思路完全一样只是语法不同。C 里可以写成类似结构排序用sort(nums.begin(), nums.end())结果用vectorvectorint保存。Java 里用Arrays.sort(nums)和ListListInteger。逻辑上唯一要注意的是内层跳过重复值的条件里nums[left] nums[left - 1]和nums[right] nums[right 1]都要放在指针移动之后顺序不要搞反。3.2 边界用例跑一遍结果全对光看代码还不够我把几个典型用例的实际执行结果列出来方便你自测。输入输出说明[][]空数组没有三元组[0][]长度不足 3[0, 0, 0][[0, 0, 0]]三个 0 是合法答案不能漏[-1, 0, 1, 2, -1, -4][[-1, -1, 2], [-1, 0, 1]]题目原始示例[-2, 0, 1, 1, 2][[-2, 0, 2], [-2, 1, 1]]重复的 1 能被正确使用两次[1, 2, -2, -1][]任意三个数加和都不为 0[0, 0, 0, 0][[0, 0, 0]]结果去重后只有一个三元组重点看一下 [-2, 0, 1, 1, 2]。排序后是 [-2, 0, 1, 1, 2]外层固定 -2left 指向 0right 指向 2和为 0记录 [-2, 0, 2]。然后 left 移到 1right 移到 1此时两个指针还没相遇sum -2 1 1 0记录 [-2, 1, 1]。由于数组里有两个 1它们分别被 left 和 right 使用恰好组成一对这也说明我们不能简单粗暴地“把重复元素去掉”。再来一个容易错的 [0, 0, 0, 0]。外层 i 0 时left 指向第二个 0right 指向最后一个 0记录 [0, 0, 0]随后 left 和 right 相遇结束。外层 i 1 时nums[1] nums[0]跳过i 2 时同样跳过。最后答案只有一个 [0, 0, 0]正确。3.3 哈希表方案也能做但为什么不如双指针很多初学者会问既然两数之和用哈希表三数之和能不能也固定一个数、再用哈希表扫剩下的数答案是能但写起来没那么爽。def threeSumHash(nums): nums.sort() ans set() n len(nums) for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue seen set() j i 1 while j n: need -nums[i] - nums[j] if need in seen: triplet tuple(sorted((nums[i], need, nums[j]))) ans.add(triplet) seen.add(nums[j]) j 1 return [list(t) for t in ans]这个方案的时间复杂度也是 O(n^2)但由于每个固定值 i 都要维护一个哈希表额外空间是 O(n)而且最终还要用 set 给三元组排序去重常数不小。如果数组里大量重复set 里会塞进很多候选三元组内存开销更大。双指针方案则不需要额外 set找解过程中就同步去重结果直接 append空间 O(1)排序栈不算效率和清晰度都更高。所以在面试中你可以提一句“哈希表是可行方案但空间更差、去重更啰嗦因此我选择排序 双指针”这本身就是加分项。4. 常见错误、排查技巧与面试加分点4.1 常见 WA 原因速查表我见过太多人在三数之和上卡住总结下来无外乎下面几类。错误现象根本原因修复方式输出结果里有重复三元组外层或内层没有跳过重复值外层比较 nums[i] 和 nums[i-1]内层找到解后 while 跳过漏掉了合法解外层去重写成比较 nums[i] 和 nums[i1]改成和前一个位置比较死循环或者运行超时找到 sum0 后只移动一个指针left 和 right 同时移动再跳过重复部分用例越界i 的循环范围写成 range(n)改为 range(n - 2)全 0 数组只输出一个结果没有理解值去重 vs 下标去重确认题目要求的是值组合[0,0,0] 只保留一个排序后漏判 nums[i] 0没用剪枝导致后续无效扫描在循环开头判断并 break这里我想单独强调第一行。很多写法是找到答案以后用while left right and nums[left] nums[left 1]: left 1然后再left 1一次。这种写法也能过但容易把指针移动和去重顺序搞混。我更推荐先在 sum 0 分支里无条件left 1和right - 1然后再用nums[left] nums[left - 1]去重因为这时 left 已经指向了新位置判断逻辑更自然。还有一种隐蔽错误外层循环虽然跳过了重复的 nums[i]但内层没有跳过重复的 nums[left] 或 nums[right]导致同一个 i 下面出现两组相同的三元组。比如 [-2, 0, 0, 2, 2] 里第一次找到 [-2, 0, 2]如果不跳过 0 和 2第二次又会找到 [-2, 0, 2]。所以内层 while 去重一定不能省。4.2 复杂度陷阱与可选的剪枝优化这道题的时间复杂度是 O(n log n) 排序 O(n^2) 双指针最终是 O(n^2)。很多文章一句话带过但实际刷题时有个隐藏成本最坏情况下所有答案都有效比如数组由大量正数和负数组成最终结果数量也可能达到 O(n^2)这时输出本身就会很大。LeetCode 的判题机制不会让你因此超时但你要理解复杂度的含义别被“双指针 O(n^2)”骗了。空间复杂度上双指针方案除了排序递归栈答案数组不算额外空间可以认为是 O(1)。如果用哈希表方案额外有一个 set 不断变大最坏 O(n)这是面试中比较有价值的对比点。可选的剪枝有两个。第一个已经写进代码里排序后nums[i] 0直接 break因为后面的数都更大不可能和为 0。第二个更精细如果nums[i] nums[i1] nums[i2] 0说明从 i 开始最小的三个数和已经大于 0那么后面任何组合都不可能等于 0可以直接 break如果nums[i] nums[n-2] nums[n-1] 0说明当前 i 作为第一个数太小和最大的两个数相加仍然小于 0直接 continue 到下一个 i。这两个剪枝在随机数据上提升不大但在一些卡常数的题目里能让代码快一点。面试时提出来能体现你对边界的思考深度。4.3 面试官真正想听什么说实话三数之和这种经典题面试官早就看过几百份答案了他不在乎你能不能默写代码在乎的是你有没有自己的分析过程。我建议按这个顺序讲先说暴力 O(n^3)点出问题在于重复扫描和去重困难然后说固定一个数转两数之和比较哈希表和双指针的取舍接着说排序为什么不会破坏正确性因为题目返回值而不是下标最后落到去重细节主动举 [-1, -1, 2] 的例子说明为什么外层不能写nums[i] nums[i1]。面试官如果问“能不能不用排序”你就回答不排序也能做固定一个数后用哈希表扫剩下的数但需要用 set 对结果三元组做唯一化空间复杂度退化到 O(n)而且每次都要排序三元组实际运行不见得比双指针快。这话一说基本 OK。还有一个冷门但常见的问题数组里重复值很多会不会影响答案数量答案是不会因为重复值作为不同下标可以被同一个值组合使用但最终值组合会被去重掉。这跟“组合”的定义有关最好顺便提一句。5. 从这道题延伸出去的刷题路线5.1 四数之和、最接近的三数之和一个模板搞定三数之和吃透了整个双指针求和系列都变得有迹可循。LeetCode 18. 四数之和就是三数之和的加强版。外层套两层循环固定前两个数内层仍然用双指针找后两个数目标值变成 target还要注意四元组去重。时间复杂度从 O(n^2) 涨到 O(n^3)思路完全一致。LeetCode 16. 最接近的三数之和也不难它不需要精确等于 0而是维护一个最小差值每次根据当前和与 target 的远近更新答案指针移动规则同样是偏大时右移、偏小时左移。LeetCode 259. 三数之和小于 K 更偏向计数找到一个区间后因为有序性可以批量统计组合数量其实就是把“找精确解”变成了“统计满足某性质的区间”。所以我一直觉得三数之和不只是“一道题”它是一个模板。你把 15 题的标准写法理解透后面 16、18 甚至 259 都是在同一个骨架上加一点条件。刷 LeetCode 热门 100 题的时候最怕的就是题与题之间孤立地背答案没有形成这种“模板感”。5.2 热门 100 题和周赛里的双指针身影双指针思想在 LeetCode 热门 100 题里到处都是比如盛最多水的容器、接雨水、删除有序数组中的重复项本质上都是通过两个指针在有序结构上做高效扫描。三数之和是其中最适合入门的一题因为它把“双指针”和“去重”这两件事同时考验了你。最近 LeetCode 周赛 430 的题解讨论里很多选手复盘自己的代码时翻来覆去就是在讲指针怎么移、条件怎么写、边界会不会越界这些基本功题听起来很基础但真到了限时环境里写错一次就要卡掉五分钟。还有一个有意思的现象LeetCode 073 爱吃香蕉的狒狒 这种题明明考的是二分查找但评论区里大家纠结最多的还是“边界条件”和“最后一次要不要再验证一遍”。这和三数之和里“去重条件写在指针移动前还是移动后”一样都是细节决定成败。所以我个人有个建议不要只刷三数之和就急着去刷难题先把 15 题的各种问法都吃透比如自己给自己出题改一下 target、改一下返回值类型、改一下允许重复的条件看看代码还能不能快速改对。能做到这一点你在周赛和面试里碰到类似题时心里就有底了。我自己在实际操作中的体会是每次写三数之和我都会先把数组排个序然后拿一张纸手动模拟一轮双指针的移动把每次 sum 的变化写出来。这个习惯帮我避开了很多“看代码以为会了一跑就错”的坑。另外一个很实用的小技巧是用-nums[i]作为内层的目标值把判断条件写成nums[left] nums[right] -nums[i]这样在逻辑上更容易和两数之和对应也不会把符号搞混。三数之和是那种值得反复写三遍的题第一遍照抄第二遍默写第三遍闭着眼睛讲思路你会发现整个双指针系列都跟着通透了。