LeetCode Hot 100榜单上的第15题“三数之和”我愿称之为“双指针入门的第一道坎”。很多人做完第1题两数之和信心满满地点开这道medium结果看到要输出“所有不重复的三元组”当场懵住还有人照着题解写本地一跑全对一提交就“输出重复”或者“漏解”。如果你也是这类情况这篇题解应该能帮你彻底想明白为什么排序之后双指针就成立了为什么去重要放在那个位置以及面试时最容易被追问的复杂度到底怎么算。本文从暴力解法开始推演把每一步思考都摊开来讲不跳步、不藏答案。不管你是刚刷LeetCode的初学者还是准备面试想快速过一遍hot100的选手这篇都值得花十分钟读完。1. 题目读完先别急着写代码几个容易忽略的约束1.1 题目到底在问什么先复述一下题目给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i、j、k互不相同且三数之和为0。要求返回所有和为0且不重复的三元组。比如输入nums [-1,0,1,2,-1,-4]答案是[[-1,-1,2],[-1,0,1]]。注意这里[-1,-1,2]里的两个-1用的是数组里两个不同位置的-1这完全合法。示例很好理解但真正的坑都藏在题面细节里。1.2 三个“隐藏规则”最容易踩坑规则一三个下标互不相同但值可以相同。这是最容易被忽略的点。很多人以为三元组里三个数必须是三个不同的值于是看到[-1,-1,2]直接当非法组合跳过。实际上题目只要求索引不同不要求值不同。数组里有两个-1那就用这两个-1只要它们的索引不同就行。这个细节直接影响去重逻辑的写法后面会专门展开。规则二返回的是数值组合不是下标。这一点决定了我们拥有极大的自由度。两数之和那道题要求返回下标所以排序会破坏位置信息往往不敢动数组但三数之和只关心数值本身数组排成什么顺序都不影响答案的正确性。换句话说我们爱怎么排序就怎么排序。这是整道题能走向排序双指针解法的前提条件。规则三答案可以有多组没有“唯一解”这回事。两数之和题目假设只有唯一答案找到一个就可以提前返回三数之和不同它要求把所有不重复的组合全部枚举出来。所以不要在设计算法时想着“找到一组就收工”你的算法必须有能力遍历所有可能且不重不漏。这三个规则叠加在一起其实已经把解题方向暗示得很明显了既然值重复不影响合法性既然可以随便排序那排序后处理连续相同元素就是最自然的去重手段。2. 暴力法为什么必挂从O(n^3)到去重困境2.1 三重循环暴力枚举最直接的思路当然是三层循环n len(nums) res [] 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: # 还需要去重 res.append([nums[i], nums[j], nums[k]])这段代码有两个致命问题。第一个问题是复杂度。数组长度在LeetCode上通常给到3000甚至更高三层循环的组合数是C(3000, 3)约45亿次。哪怕每次操作只需要1纳秒也要跑45秒更别说实际常数远大于此。这已经不是“能不能优化”的问题而是根本不可能跑完。第二个问题比复杂度更隐蔽就是去重。暴力枚举出来的结果里会有大量重复比如[-1, 0, 1]可能以[0, -1, 1]、[1, 0, -1]等各种顺序出现而这些组合本质上同一个三元组。2.2 从“怎么判重”到“为什么需要排序”那怎么判重一个朴素的想法是把每个三元组内部排序然后作为字符串或者元组塞进Set。比如[-1,0,1]内部排序后还是[-1,0,1][1,-1,0]排序后也是[-1,0,1]于是两者就能判成重复。这个方法理论上可行但代码相当繁琐而且排序哈希的常数开销很大三重循环本来就已经跑不动了再叠加Set去重复杂度更爆炸。不过这个判重思路给了我们一个关键启发既然最终答案里每个三元组都要按统一顺序比较那不如一开始就把整个数组排好序。数组排序之后任何合法三元组里的三个数天然就是升序的不同组合之间比较起来极其容易。更妙的是排序后相同的数值会聚集在一起我们可以通过“跳过连续重复元素”的方式把重复组合在源头就掐断而不是枚举完再去重。这一步思维转换是从暴力法走向最优解的灵魂。排序不是为了让双指针成立排序首先是为了让去重变得便宜。3. 排序加双指针这道题的标准解法长什么样3.1 为什么是“排序双指针”而不是“排序哈希”固定第一个数nums[i]之后问题立刻变成在i右侧的区间里找两个不同的数使它们的和等于-nums[i]。这是一个经典的两数之和问题而且区间是有序的。有人会问两数之和我熟啊用哈希表一次遍历就搞定了为什么这里不继续用哈希两数之和那道题用哈希表是因为它要求返回下标且假设唯一解。三数之和这边要求返回所有不重复的值组合。用哈希表当然也能做对每个nums[i]在剩余区间里跑一遍两数之和哈希法最后再用Set去重。但这样干代码会长一截而且Set去重本身有额外开销。排序双指针的优势在于它利用有序数组的单调性在一次线性扫描里就能找齐所有配对而且天然支持跳过重复值去重逻辑简单到只有几行。所以这道题的正确姿势就是先把数组排序再固定一个数剩下两个数用双指针。3.2 双指针移动的完整逻辑具体步骤拆开讲对数组升序排序。外层循环固定第一个数nums[i]i从0遍历到n-3。初始化左指针left i 1右指针right n - 1。计算sum nums[i] nums[left] nums[right]若sum 0记录这个三元组然后去重并移动双指针若sum 0说明整体偏小需要更大的数只有left右移才能让和变大若sum 0说明整体偏大需要更小的数只有right左移才能让和变小。为什么偏小时只能动left因为数组有序right左移只会让数更小和只会更小不可能逼近0left右移才会增大和。反过来偏大时只能动right。这个决策不是猜的而是严格由数组的单调性决定的。光说理论不够我们拿示例走一遍。排序后nums [-4,-1,-1,0,1,2]i0指向-4需要在右侧找两个数和为4。left-1, right2和是-3偏小left右移一路走-12-3、022、123都到不了4这轮无解。i1指向-1需要在右侧找两个数和为1。left-1, right2-121命中记录[-1,-1,2]然后去重移动。接着left0, right1011命中记录[-1,0,1]。i2仍指向-1与i1重复跳过。后续i不再有解。最终得到[[-1,-1,2],[-1,0,1]]和答案完全一致。3.3 为什么双指针不漏解这是面试官最爱追问的点双指针凭什么敢保证不重不漏关键在于每一步都排除了一个“不可能成为答案”的候选位置。假设当前sum target我们已经知道nums[left] nums[right]不够大。此时right已经是区间里最大的数了把right配上当前left都不够那当前left配上任何更小的数更不可能够。所以以当前left为较小数的所有组合都可以直接排除于是left。反之sum target时当前right配上最大的left其实是当前区间里能配的最大数都超了那当前right配上任何更大的更不可能所以right--。每一步至少排除一个元素整个过程是线性推进的不会漏掉任何一个可能恰好等于target的组合。这个“单调性排除法”的论证是双指针算法正确性的根基建议记牢。4. 去重是灵魂90%的人写错的都是这里4.1 最经典的去重错误i和i1比较很多人拿到这道题会直觉地写下这样的去重逻辑if (nums[i] nums[i 1]) continue; // 错误写法这行代码的本意是“如果当前值和下一个值一样说明开头重复跳过”。但它会在关键时刻误杀正确答案。用一个经典例子演示nums [-1, -1, 2]。排序后还是[-1, -1, 2]。正确答案是[-1, -1, 2]因为两个不同位置的-1加上一个2刚好凑成0。但用nums[i] nums[i 1]判断会发生什么i0时nums[0] nums[1]都是-1于是continuei1时nums[1] -1nums[2] 2不相等进入双指针但此时left2, right2left right不成立循环直接结束。最终结果空数组。正确答案被活生生跳过了。问题出在哪用i1判断意味着“只要当前值和下一个值相同就放弃以当前值为开头的所有枚举”。但当数组里有两个-1、且这两个-1能组合出[-1,-1,2]时以-1开头是有合法答案的而且这个答案必须被枚举一次。用i1判断把这次唯一的枚举机会也抹掉了。4.2 正解与i-1比较正确的写法是if (i 0 nums[i] nums[i - 1]) continue;含义完全不同如果当前值和上一个已经处理过的值相同说明以这个值为开头的所有三元组在上一轮i里已经完整枚举过了。现在再用相同的开头值枚举得到的只会是重复答案所以跳过。同样用[-1, -1, 2]验证i0时i 0不成立不跳过正常枚举得到[-1,-1,2]i1时nums[1] nums[0]跳过避免再输出一份[-1,-1,2]。完美。这个区别非常重要我直接在表格里把两种写法对比一下判断写法实际效果风险nums[i] nums[i 1]跳过以当前值开头的全部枚举漏解比如[-1,-1,2]nums[i] nums[i - 1]跳过与上一个开头值重复的枚举正确保留第一次枚举机会一句话总结外层去重要和已经处理过的i-1比不能和还没处理的i1比。4.3 内层双指针的去重时机外层去重搞定之后内层还有一重去重很多人栽在这里。先看正确做法在sum 0命中答案之后while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--;为什么去重要放在命中之后而不是循环开始前因为只有在命中之后我们才确定“这个值的配对已经被记录过了”。此后left再遇到相同值、right再遇到相同值组合出来一定还是同一个三元组属于重复答案必须跳过。而命中之前相同值可能配合不同的i产生不同结果提前跳过反而可能漏解。举例说明nums [-2, 0, 0, 2, 2]排序后不变。i0指向-2要找两个数和为2。如果在一开始就无脑跳过重复的0把left直接推到第一个2那就永远得不到[-2, 0, 2]这个正确答案。正确的做法是让left停在第一个0先命中[-2, 0, 2]再通过去重跳到另一个位置。内层去重还有两个容易错的地方一是边界条件。while内部一定要检查left right否则数组元素全相同的时候会越界。比如nums [0,0,0]命中一次后去重循环如果没判边界left可能一路冲到数组尾部。二是去重和指针移动的顺序。正确顺序是“先跳过重复值再统一移动一格”。拿左指针举例while结束后left停在重复段的最后一个位置这时再left就稳稳落到下一个新值上。如果先left再去重很容易跳过整个重复段后还得再额外处理逻辑容易乱。5. 完整代码实现与边界用例5.1 Java参考实现把上面的所有思路整合成完整代码class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger ans new ArrayList(); int n nums.length; if (n 3) return ans; Arrays.sort(nums); for (int i 0; i n - 2; i) { // 剪枝开头已经大于0后面都是正数三数之和不可能为0 if (nums[i] 0) break; // 外层去重与已处理过的i-1比较 if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { ans.add(Arrays.asList(nums[i], nums[left], nums[right])); // 内层去重跳过连续相同元素 while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return ans; } }这段代码有几个细节值得注意nums[i] 0这个剪枝非常实用。因为数组已经升序排序当固定值都大于0时后面所有数都比它大三个正数相加永远不可能等于0直接break掉整个循环。这一行代码在极端情况下能省掉大量无效计算。另外left right在去重while里出现两次不是冗余而是必须。如果数组里大量重复元素比如[0,0,0,0]命中[0,0,0]之后去重left会一路右移right一路左移没有边界判断就会越界导致运行时错误。5.2 Python参考实现class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: nums.sort() n len(nums) ans [] for i in range(n - 2): 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: 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 elif s 0: left 1 else: right - 1 return ansPython版本和Java版本逻辑完全一致只有语法差异。nums.sort()是原地排序不需要接收返回值这是一个小细节很多新手会写成nums sorted(nums)也能跑但多了一次不必要的变量绑定。5.3 边界用例跑一遍写完代码不能直接提交先用几个边界用例自测输入输出说明[][]空数组直接返回空[1, -1][]长度不足3直接返回空[0, 0, 0][[0, 0, 0]]最小合法用例[0, 0, 0, 0][[0, 0, 0]]多个0只输出一组验证去重[-1, -1, 2][[-1, -1, 2]]验证外层去重用i-1而不是i1[-2, 0, 0, 2, 2][[-2, 0, 2]]验证内层去重不能提前[-4, -1, -1, 0, 1, 2][[-1, -1, 2], [-1, 0, 1]]标准示例这些用例在本地都能跑出预期结果再提交LeetCode基本就稳了。个人经验是写算法题至少准备三组测试一组是标准示例一组是极端重复一组是临界长度。这三组过了大部分隐藏用例都能扛住。6. 复杂度、进阶优化与同类题目的通解思路6.1 时间与空间复杂度时间复杂度分两块排序O(n log n)外层循环固定i需要O(n)每次循环内部双指针扫描区间需要O(n)所以枚举部分是O(n^2)。整体复杂度取最高阶就是O(n^2)。相比暴力的O(n^3)这是一个档次上的提升。n 3000时n^2 9e6现代机器轻松跑完这也是这道题能成为hot100常客的原因——复杂度够优秀实现又够考验细节。空间复杂度方面不算答案数组的话主要开销来自排序算法。Java的Arrays.sort对原始类型数组使用的是双轴快排递归栈深度是O(log n)如果语言实现用的是堆排序可以做到O(1)。所以一般回答O(log n)或O(1)都能接受。答案数组本身占用的空间取决于有多少组解最坏情况下可能达到O(n^2)级别但面试时通常会说明“不计入额外空间”。6.2 两个可选的剪枝优化除了nums[i] 0这个最常见的剪枝还有两个更细的优化可以加最小三数和剪枝如果nums[i] nums[i1] nums[i2] 0说明从i开始最小的三个数加起来都大于0后面任何组合都不可能等于0直接break。最大两数和剪枝如果nums[i] nums[n-2] nums[n-1] 0说明当前i配上数组里最大的两个数都还是负数那i太小了任何组合都不可能凑到0直接continue换下一个i。这两个剪枝不影响正确性只是减少无效枚举。实测下来对于随机数据能省一些时间但对LeetCode的用例来说不加也能过。它们更大的价值在于展示你理解了这个算法的边界面试时可以在优化部分主动提出来。6.3 从二数到N数之和的通解思路三数之和不是孤立的题它属于一整个家族。LeetCode 1 两数之和哈希表O(n)但要求返回下标且只有唯一解。LeetCode 167 两数之和II输入有序数组双指针O(n)因为输入天然有序。LeetCode 16 最接近的三数之和排序双指针维护最小差值思路几乎一模一样。LeetCode 18 四数之和排序双指针外层多套一层循环先固定两个数后两个数用双指针复杂度O(n^3)。发现规律了吧N数之和N≥3的通用解法是先排序固定N-2个数最后两个数用双指针。每多固定一个数复杂度就多乘一个n。三数之和是O(n^2)四数之和是O(n^3)以此类推。理解了这条主线你刷LeetCode时会把很多题串成一张网而不是一道一道孤零零地背答案。至于我个人刷这道题的真实体会去重逻辑真的别死记硬背把[-1,-1,2]这个反例写进自己的错题本每次写错看一眼就全想起来了。这种“用一个反例守护一段逻辑”的方法比背十遍代码都管用。如果你也是刷题容易“看了答案就懂、自己写就废”的类型建议把双指针移动的条件和去重的时机用自己的话在注释里写一遍再删掉那才算真正过脑子了。