三数之和双指针解法：排序去重与O(n²)优化实践

1. 题目理解与整体思路

1.1 三数之和到底是什么问题

先把这个题说人话。给定一个整数数组nums，让你找出所有三个数相加等于 0 的组合，而且要求返回的三元组不重复。比如[-1, 0, 1, 2, -1, -4]，结果就是[-1, -1, 2]和[-1, 0, 1]，注意[-1, 0, 1]不能因为数组里有两个-1就算两次。

看起来是不是很简单？暴力三重循环确实能做，嵌套遍历三次把所有组合都找出来，然后去重。但题目只要稍微把数据量放大一点，比如两三千个元素，三重循环直接超时。这道题的经典之处就在于：它考察的不是“你会不会枚举”，而是“你能不能把 O(n³) 的做法优化到 O(n²)”，同时还得处理一个特别让人头疼的细节——去重。

我在刷题笔记里把今天标记为 Day2，因为这道题是双指针系列里最典型的入门题。如果你把这道题吃透了，后面遇到“最接近的三数之和”“四数之和”这些变种，基本就是换汤不换药。

1.2 为什么这道题值得单独写一篇

说实话，LeetCode 上比三数之和难的题多的是，但这道题有一个特点：细节决定成败。我见过很多能写出双指针框架的人，结果卡在去重逻辑上，边界一调就错。你以为你在处理数组下标，其实你在处理一堆容易混淆的“相等情况”。

这道题也很适合用来检验一个人对“有序数据”的敏感度。数组无序时，你要找三数之和为 0，只能用哈希表辅助，或者暴力枚举；数组有序时，你就可以用双指针从两端向中间逼近。这个思想在“两数之和 II”“盛最多水的容器”这些题里都反复出现。

另外，三数之和的面试出场率特别高。很多公司把它当作“你会不会优化穷举”的试金石，或者用来考察你处理边界条件和输入输出的能力。不管你是准备面试还是单纯练算法基本功，这道题都绕不开。

2. 解法思路与核心原理拆解

2.1 为什么首选固定一个数 + 双指针

先想清楚这道题的数学结构：我们要找a + b + c = 0，等价于固定其中一个数a，然后找b + c = -a。这样一来，问题就从“三数之和”降级成了“两数之和”。而“两数之和”在一个有序数组里用双指针做，是 O(n) 的时间复杂度，外层再遍历固定a，整体就是 O(n²)。

那为什么不用哈希表做两数之和？两数之和用哈希表确实能做到 O(n)，但三数之和如果用哈希表，会在去重环节付出额外代价。因为你不仅要记录值，还要记录下标，而且结果里不能有重复三元组。哈希表在这里处理起来容易乱，代码写出来又长又容易出 bug。排序 + 双指针的优势是：去重的逻辑可以顺便通过“跳过相同元素”来解决，不需要额外的集合结构。

这里有一个很重要的前提：数组必须先排序。排序的代价是 O(n log n)，但在 n 比较大的时候，这个代价是可以接受的，因为它换来了双指针的线性的扫描效率。

2.2 双指针收缩的数学逻辑

很多人知道双指针怎么写，但不知道为什么这么写是对的。我仔细说一下这个逻辑，理解了之后你就不会乱改指针了。

假设数组从小到大排好序，外层指针i固定住第一个数，然后让左指针left = i + 1，右指针right = len(nums) - 1，从剩下的区间两端往中间走。每一次计算sum = nums[i] + nums[left] + nums[right]：

• sum == 0：说明找到一组答案，记录结果，然后left右移、right左移，继续找其他组合。
• sum < 0：说明总和太小了。数组是有序的，右边已经是最大的数，想让总和变大，只能把left往右移动，尝试更大的数。
• sum > 0：说明总和太大了。想让总和变小，只能把right往左移动，尝试更小的数。

这个逻辑看起来很直觉，但它背后有一个隐藏条件：数组有序。如果没有排序，sum < 0时你根本不知道移动哪个指针能接近零。排序让“移动指针”这件事有了确定的数学方向，这是整个算法的根基。

为了让你更直观地理解，我打个比方。想象你有一排从矮到高排列的人，你站在队伍左侧第二个位置，让最左边和最右边的人分别出列，三个人身高之和如果不够 180，就把左边的人换成一个更高的；如果超过 180，就把右边的人换成一个更矮的。每一次调整都在向目标靠近，而且不会漏掉任何组合。

2.3 为什么哈希表方案不那么推荐

也不是说哈希表完全不行，我自己早期写三数之和也用过哈希表，当时思路很简单：先把所有元素放进哈希表，然后双重循环枚举前两个数，查表找第三个数。但遇到的问题很现实：

• 哈希表存下标的话，需要处理同一个元素被重复使用的情况。比如nums = [0, 0, 0]，你枚举前两个都是下标 0 的 0，第三个查表又查到下标 0 的 0，结果自己和自己组合了。
• 就算你给哈希表存的是“值和出现次数”，去重依然很麻烦。两组三元组只要元素相同就重复，哈希表没法直接判断，你要么把所有结果存到 Set 里，要么排序后逐个比较。
• 更麻烦的是，当数组里有大量重复值时，哈希表方案的时间复杂度会退化得很快，实际跑起来不一定比双指针快。

所以我个人的结论非常明确：三数之和的最优解就是排序 + 双指针。哈希表可以用来解决“两数之和”这种不需要去重的问题，但三数之和这种带去重要求的，双指针是更稳定、更简洁的选择。

3. 实操全过程：从暴力到双指针

3.1 先写一个暴力解法找感觉

我建议你不管最终用什么思路，第一步都先写一个最容易理解的暴力版本。这不是浪费时间，而是帮你确认题目要求，尤其是“不重复三元组”这个条件到底意味着什么。

def three_sum_bruteforce(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

这个版本很好地完成了两件事：第一，验证你对题意的理解有没有偏差；第二，提供一个 baseline，让你能用它来对拍验证双指针版本的正确性。暴力版本的时间复杂度是 O(n³)，数据量小的时候没问题，但只要n超过几百，就会明显变慢。

我当时做的时候，拿暴力版本生成了大量随机小数组的答案，再用双指针版本跑同样的输入，逐一对比结果。这个对拍过程帮了我大忙，因为去重边界很容易在某个特殊用例上翻车，暴力版本就是最好的“标准答案”。

3.2 排序 + 双指针的标准写法

下面这个是 Python 的标准实现，我建议你直接看代码，然后跟着我一起逐步拆解：

def three_sum(nums): nums.sort() n = len(nums) res = [] 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: 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()，原地排序，要记得排序会直接修改原数组。
• 外层循环从0到n - 3，因为至少要留两个位置给左右指针。
• nums[i] > 0时直接break，排序后后面的数都比 0 大，三数之和不可能为 0，这是剪枝。
• 跳过i的重复值，避免同一个固定数被重复处理。
• 找到一组答案后，还要跳过left和right的重复值，因为数组里可能有多个相同的数。

这个代码跑在[-1, 0, 1, 2, -1, -4]上，输出是[[-1, -1, 2], [-1, 0, 1]]，和题目预期完全一致。

3.3 每一步操作的意图注释

很多教程只给你代码，不告诉你为什么每一步要这样写。我把自己写这版代码时脑子里的思考过程按顺序记录下来，你写的时候也可以这样提醒自己。

第一，为什么i最大到n - 3？因为left最小是i + 1，right最大是n - 1，如果i = n - 2，那么left = n - 1，此时left和right重合，根本凑不出三个不同的数。i = n - 3时，left = n - 2，right = n - 1，刚好还能组成三个数的组合。

第二，为什么nums[i] > 0能直接break而不是continue？因为数组已经排序，nums[i]后面的数都比它大，既然它已经大于 0，后面的三个数之和一定大于 0，不可能有解。这里用break是合理的剪枝，而不是只跳过当前i。

第三，两种跳过重复的写法有什么区别？外层跳过nums[i]用的是“看前一个”，内层跳过nums[left]和nums[right]用的是“看后一个”。方向不同是因为一个是为了避免在固定数相同的情况下重复执行整个内层循环，另一个是为了避免在已经找到一组答案后继续用相同的左右指针值再算一遍。本质上都是在说同一个事：相等的值只处理一次。

4. 常见问题与排查技巧实录

4.1 去重逻辑到底怎么想才不会错

这是三数之和最大的坑，我敢说至少有一半的人第一次写都是错在去重上。

先看一个最常见的错误写法：在sum == 0后，直接left += 1、right -= 1，不跳过重复值。这样会导致什么问题？假设数组是[-2, 1, 1, 1, 1]，固定i = 0即-2，第一次找到left = 1, right = 4，得到[-2, 1, 1]；然后left变成 2、right变成 3，数组下标 2 和 3 的值还是 1 和 1，又找到一个[-2, 1, 1]。同一个三元组被记录了两次，结果重复。

另一个常见错误是：在left和right移动时，用while nums[left] == nums[left + 1]但忘了加left < right的条件。我在前期写的时候就踩过这个坑，万一数组里都是相同元素，指针会一路滑到数组末尾，导致IndexError。所以内层去重循环的条件一定要带上left < right。

再一个常见错误是：在判断sum < 0或sum > 0时也去重。这其实没必要，因为只有找到一组答案时才需要考虑重复记录的问题。如果你在total < 0时也加跳过逻辑，会跳掉一些本来有效的组合，结果反而漏解。

去重的核心原则就一句话：同一层循环里，值相同的元素只处理一次。外层固定数相同就跳过，内层找到答案后左右指针遇到相同值就跳过。只要这两点做到，结果天然不会重复。

4.2 边界情况一网打尽

我整理了一个用来验证代码正确性的测试用例清单，你可以直接拿来用。这几个 case 覆盖了最常见的边界问题：

其中[0, 0, 0, 0]是最容易出错的。如果你按暴力 + Set 的方法，可能还不会重复；但如果双指针边界没处理好，很可能输出多组[0, 0, 0]。我的代码里，外层i = 0处理完后，i变成 1 时因为nums[1] == nums[0]会直接continue，这就保证只处理一次固定数。内层找到答案后左右指针也各自跳过重复，所以整道题只会输出一组[0, 0, 0]。

4.3 性能表现与复杂度分析

我拿三个不同量级的数组测了一下排序 + 双指针版本的运行时间，给你做个参考：

• n = 100：几乎瞬间完成，暴力法也看不出区别。
• n = 1000：双指针大约几十毫秒，暴力法已经要跑好几秒。
• n = 3000：双指针大约几百毫秒，暴力法基本已经跑不动。

时间复杂度的推导是这样的：外层循环从 0 到n-3，内层left和right从两端向中间扫描，每次循环至少移动一个指针，所以内层是 O(n)。整体 O(n²)。排序 O(n log n) 被包含在大 O 里当作优化步骤，不影响最终平方级复杂度。空间复杂度方面，除了结果数组，只用了几个变量，所以是 O(1) 到 O(n) 之间（取决于结果集的大小，如果你把结果也算进去就是 O(n) 级别的输出空间）。

双指针版本之所以比暴力法有质的提升，核心在于内层从“枚举两个数”变成了“在一个有序区间里线性扫描”，组合数量从 C(n,2) 降到了 n。这个思想在很多题里都能复用，我后面写四数之和的时候直接套了同样的框架，只是外层多加了一层循环。

4.4 面试中容易被追问的细节

如果你是在面试场合写这道题，下面几个点经常会成为追问的素材。提前想清楚，回答的时候会从容很多：

1. 为什么先排序？如果不排序，双指针为什么不能用？——因为双指针依赖数组的有序性来指导移动方向。
2. 去重为什么放在找到答案之后？放在前面行不行？——放在前面有可能跳过合法组合。
3. 这个算法能不能处理全是负数的数组？——可以，比如[-5, -4, -3]，排序后固定i，双指针区间里全是负数，三数之和始终小于 0，最后返回空列表，没问题。
4. 如果要求输出三元组内部也排序，怎么做？——排序整个数组后，固定数、左指针、右指针本身就是按顺序取值的，所以三元组天然是升序的，不需要额外处理。

我遇到过不少人能写出代码，但答不上来“为什么去重逻辑要放在这个位置”。所以不要只背代码，要把每一个if和while背后的动机想明白。

5. 个人实操经验与进阶建议

5.1 这道题的代码迭代过程

我第一次独立写三数之和时，用的是“固定一个数 + 剩余两数之和用哈希表”的思路，结果代码写了快四十行，去重逻辑绕来绕去，测试[0, 0, 0, 0]的时候就崩了。后来我回头去查别人的题解，发现排序 + 双指针的实现如此简洁，才意识到问题不是“我不会用哈希表”，而是“我选错了工具”。

从那以后，我养成一个习惯：遇到一个题，先分析清楚约束条件，再决定用什么数据结构和算法，而不是一上来就写代码。三数之和的约束是“结果不重复”，这直接决定了排序 + 双指针是比哈希表更好的方案。因为有序数组天然把“相同值”放在相邻位置，跳过重复变得非常自然。

5.2 验证代码正确性的小技巧

我强烈建议你做一个“对拍验证”脚本。简单来说，就是同时写一个简单的暴力解和一个优化解，然后生成大量随机数组，比较两个版本的结果是否完全一致。这个习惯在我刷算法题时帮了我大忙。

对拍的做法很简单：随机生成一个长度 5 到 20、元素范围 -10 到 10 的数组，分别跑暴力版和双指针版，比较结果。如果有不一致，说明你的优化版有问题，再用那个随机数组作为测试用例去调试。等对拍跑了几百组随机用例都没问题之后，再去 LeetCode 提交，基本一次就过。

import random def generate_random_array(): n = random.randint(5, 20) return [random.randint(-10, 10) for _ in range(n)] # 循环跑对拍……

这个小技巧不仅适用于三数之和，也适用于其他涉及边界和去重的题目。别觉得多写一个暴力版是浪费时间，它在解决问题时可能是最省时间的方式。

5.3 后续可以继续扩展的方向

三数之和不是孤立的一道题，它是一个系列的开头。如果你今天能把双指针思路完全吃透，后面这些题会轻松很多：

• 两数之和 II（输入有序数组）：就是三数之和里的内层循环单独拿出来。
• 最接近的三数之和：把“等于 0”改成“最接近 target”，更新判断逻辑，框架不变。
• 四数之和：固定两个数，剩下两个数用双指针，去重逻辑再复制一层。
• 有效三角形的个数：也是先排序再用双指针，只是判断条件变成了两边之和大于第三边。

我自己的刷题节奏是：每做一道经典题，就把它的变种列出来，看看核心框架能复用多少。三数之和这道题，几乎把双指针的所有关键技巧都涵盖了，值得花时间彻底搞懂。

最后分享一个实操中的小经验：在 LeetCode 上提交之前，先亲手跑一遍[0, 0, 0, 0]和[-1, -1, -1, 2]这两个用例。能正确处理这两个用例，去重逻辑大概率就是对的。我当时写完代码后，就是靠这两个用例发现了自己的去重遗漏，改完一遍通过。希望你少走这些弯路。