企业官网建设流程全解析

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 两个指针分别指向 i+1 和 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[i+1]。

这个区别非常关键。拿 [-1, -1, 2] 举例，数组排序后就是 [-1, -1, 2]。如果写成if nums[i] == nums[i+1]: continue，当 i = 0 时，nums[0] == nums[1] 为真，直接跳过，结果就是漏掉了 [-1, -1, 2] 这个合法答案。正确的写法是“当前这个值和上一个值相同就跳过”，因为上一个值已经作为第一个数完成过一轮完整的双指针扫描了，再用同样的值做第一个数，找出来的三元组必然和上一轮重复。

第二个去重位置在内层：找到一个 sum = 0 的组合后，left 向右移动、right 向左移动，然后分别跳过和移动前位置值相同的元素。举例说明，数组 [-2, 0, 0, 2, 2]，找到 [-2, 0, 2] 后，left 从 0 移到下一个 0，right 从 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 + 1，right 至少是 i + 2，所以 i 最大到 n - 3。内层 while 的判断条件是left < right，两指针相遇时停止。

如果你用的是 C++ 或 Java，思路完全一样，只是语法不同。C++ 里可以写成类似结构，排序用sort(nums.begin(), nums.end())，结果用vector<vector<int>>保存。Java 里用Arrays.sort(nums)和List<List<Integer>>。逻辑上唯一要注意的是，内层跳过重复值的条件里，nums[left] == nums[left - 1]和nums[right] == nums[right + 1]都要放在指针移动之后，顺序不要搞反。

3.2 边界用例跑一遍，结果全对

光看代码还不够，我把几个典型用例的实际执行结果列出来，方便你自测。

重点看一下 [-2, 0, 1, 1, 2]。排序后是 [-2, 0, 1, 1, 2]，外层固定 -2，left 指向 0，right 指向 2，和为 0，记录 [-2, 0, 2]。然后 left 移到 1，right 移到 1，此时两个指针还没相遇，sum = -2 + 1 + 1 = 0，记录 [-2, 1, 1]。由于数组里有两个 1，它们分别被 left 和 right 使用，恰好组成一对，这也说明我们不能简单粗暴地“把重复元素去掉”。

再来一个容易错的 [0, 0, 0, 0]。外层 i = 0 时，left 指向第二个 0，right 指向最后一个 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 原因速查表

我见过太多人在三数之和上卡住，总结下来无外乎下面几类。

这里我想单独强调第一行。很多写法是找到答案以后用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[i+1] + nums[i+2] > 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[i+1]。

面试官如果问“能不能不用排序”，你就回答：不排序也能做，固定一个数后用哈希表扫剩下的数，但需要用 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]，这样在逻辑上更容易和两数之和对应，也不会把符号搞混。三数之和是那种值得反复写三遍的题，第一遍照抄，第二遍默写，第三遍闭着眼睛讲思路，你会发现整个双指针系列都跟着通透了。