很多人第一次刷到“三数之和”这道题，是在找工作的笔试题里。当时我还在想，这不就是三重循环套一下的事吗？等到自己真被问到“三数之和”并要在白板上手写完整解法时，才发现这题的考察点根本不是“会不会三重循环”，而是你在约束条件里能不能看出优化空间。我见过有人在笔试里用暴力三重循环跑过了小规模用例，最后卡在大数据集上超时；也有人写出来了双指针版本，却因为去重逻辑不严谨，导致结果里全是重复三元组。这道题的价值就在于此：它小，但它把排序、双指针、去重、边界条件全串起来了，是刷题和面试的一道标准分水岭。
这篇文章不打算只给一段能通过的代码，而是要讲清楚这套解法的来龙去脉：为什么要排序、双指针为什么能成立、去重到底去的是什么、实际调试中容易踩哪些坑。适合正在刷题找工作的读者，也适合想弄懂“双指针到底在干什么”而不是单纯背下答案的人。我更希望的是，你看完以后能自己推演出来，而不是只会复制粘贴。
1. 为什么“能暴力解”的题反而最考察基本功
1.1 题目描述里藏着真正的考点
题目本身很简单：给你一个整数数组，找出所有不重复的三元组，满足三个数相加等于0。比如输入[-1, 0, 1, 2, -1, -4]，符合条件的组合是[-1, -1, 2]和[-1, 0, 1]。
注意“不重复”三个字，它才是这道题的门槛。很多人第一眼看到“不重复”觉得无所谓，反正找出组合然后用集合去重呗。但当你面对一个长度是3000的数组时，先暴力枚举所有组合，再扔进集合去重，中间产生的海量临时数据会直接把内存和时间撑爆。
这道题真正的考点可以拆成三块：
- 你能不能识别出暴力法的复杂度瓶颈；
- 你能不能借助排序把无序搜索变成有序搜索；
- 你能不能在不借助外部集合的前提下，通过指针移动天然避开重复结果。
考察的不是会写循环，而是你有没有“先分析数据规律再写代码”的习惯。
1.2 为什么它是笔试和面试的高频题
三数之和几乎出现在每一套主流刷题清单里，不是因为它难，而是因为它处在“简单题”和“难题”的中间地带，最能暴露一个人写代码的真实水平。
我遇到过不少候选人，一上来就说“我用哈希表存两数之和”，这其实是一个很好但也很容易失控的方向。用哈希表做两数之和确实能降低一维复杂度，但三数之和一旦套用，你还要额外处理重复组合和哈希冲突，代码量翻倍，出错概率也翻倍。相比之下，排序加双指针的思路更简洁，也更容易证明正确性。
另外这道题的实现过程还牵涉大量细节：指针移动的时机、跳过重复元素的位置、负数与边界处理、空数组和长度不足的防御。这些细节恰恰是日常工程里最常见的bug来源，所以面试官爱考它，本质上是想通过它看你处理边界问题的肌肉记忆。
1.3 关于输入规模的直觉：3000不是随便写的
我早期刷题时很困惑，为什么不少题目的数组长度总是3000？后来才意识到，这是有讲究的。
假设数组长度是3000，三重循环的执行次数大约是3000^3 / 6，约等于45亿次基本操作。普通语言的for循环每秒大概能执行几千万到上亿次，45亿次意味着几十秒甚至几分钟的耗时，在在线评测系统里有严格的时限，几秒内跑不完就直接判超时。而排序加双指针的复杂度是O(n^2)，3000的平方是900万，加上常数操作也就几百万到一千万级别，毫秒级就能跑完。
暴力解法不是不能跑，是跑不完。这个直觉会影响你以后面对任何“能解但会超时”的算法题：先把数据规模代入复杂度公式，谁大谁小一算便知。
2. 排序是第二步之前的那一步：双指针为什么能成立
2.1 无序数组的困境：你只能穷举
如果数组是无序的，你现在想找三数和为0，有什么办法？答案是几乎只能穷举。你要固定第一个数，然后在剩下的数里找两个数之和等于它的相反数。问题是“剩下的数”里不存在任何可以快速排除的区域，你只能扫描一遍又一遍。
这就像你在一个没有编号的档案柜里找某个人，只能一份一份翻。而排序相当于给档案柜按姓氏做了编号，你一翻就能知道该往左还是往右。
哈希表解法某种程度上也是一种“给档案编号”的方式，但它引入的是额外的存储结构，而且对重复组合的处理更麻烦。排序加双指针的优势在于：它把“查找”变成了“收缩区间”，靠数据本身的单调性来排除不可能的组合。
2.2 排序以后，数据的单调性给了我们方向
我们先把数组排序。排完以后，数组变成了从负到正的递增序列。现在假设你固定了第一个数为nums[i]，问题变成：在i右边的区间里，找两个数nums[left]和nums[right]，让它们的和等于-nums[i]。
因为区间内所有数都是递增的，所以我们有两条确定的信息：
- 左指针向右移动，两数之和会变大；
- 右指针向左移动，两数之和会变小。
这里用的还是双指针那个经典的“两数之和”思想：left指向区间最小值，right指向区间最大值。如果当前两数和偏大，说明右指针的值太大了，需要左移；如果偏小，说明左指针的值太小了，需要右移。每一步移动都会排除掉一部分不可能组合，比逐个枚举高一个维度。
值得注意的是，为什么固定第一个数、然后把问题降维成两数之和是可行的？因为当数组有序以后，你完全知道左指针右侧的数的相对大小，移动方向不是猜的，是根据当前和与目标值的差值确定的。这个逻辑成立的前提只有一个：数组从一开始就必须有序。
2.3 复杂度账本：从 O(n^3) 到 O(n^2) 的差距有多大
我们可以算一笔具体账。假设数组长度是10000，暴力三重循环要执行约1.67 * 10^11次操作，当前的单核CPU要跑几十秒到几分钟。排序加双指针是两层循环，外层固定主元素，内层双指针扫描整个区间，大约是10^8次操作，配合剪枝实际运行时间在百毫秒量级。
这里还有一个隐藏收益：排序一次，可以被复用到内层循环的每一次扫描里。也就是说，多花一次排序的时间，换来的是内层循环从“枚举两数”变成“线性扫描”。
| 解法 | 时间复杂度 | 空间复杂度 | 10000长度数据估时 |
|---|---|---|---|
| 暴力三重循环 | O(n^3) | O(1) | 数分钟级 |
| 哈希表缓存两数和 | O(n^2) | O(n) | 数百毫秒级，但重复处理繁琐 |
| 排序 + 双指针 | O(n^2) | O(1)（不计输出） | 百毫秒级 |
这也解释了一个经验法则：很多看起来需要“找几个数凑目标值”的题，排序永远是第一个该考虑的预处理，而不是急着上哈希表。
3. 标准解法手写详解：三处去重与两处剪枝
3.1 完整代码：先记住骨架，再理解细节
以C++版本为例：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; int n = nums.size(); if (n < 3) return res; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; 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) { res.push_back({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 res; } };Python版本逻辑完全一致，只是语法不同：
def threeSum(nums): res = [] n = len(nums) if n < 3: return res nums.sort() 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: total = nums[i] + nums[left] + nums[right] if total == 0: 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 elif total < 0: left += 1 else: right -= 1 return res骨架说穿了就三层：排序，一层for循环固定主元素，一层while循环做双指针收敛。去了重、加了剪枝，也就这么点东西。
3.2 去重的三个关键位置，一个都不能少
去重是三数之和最容易出问题的地方。我见过的错误写法，多数是把去重条件写成了nums[i] == nums[i+1]，或者只在内层去重忘了外层去重。
先去重逻辑一共三个位置：
第一个位置：外层主元素去重。
if (i > 0 && nums[i] == nums[i - 1]) continue;注意这里比较的是当前元素和前一个元素。如果改成nums[i] == nums[i+1]，你会直接跳过一组潜在正确解。举个例子，[-1, -1, 2]这个三元组里，两个-1分别由主元素和左指针承担。如果主元素位置直接跳过第二个-1，那一组解就白白丢了。所以外层去重必须用“和前一个比较”，确保第一个-1能被正常处理。
第二个位置：匹配成功后的左指针去重。
while (left < right && nums[left] == nums[left + 1]) ++left;匹配成功时，说明当前三个数已经构成一组解。如果nums[left]和它右边下一个元素相同，那左指针移过去以后，新的三元组只是把这一个位置的数换成了同样的数，结果必然重复。所以先在原地跳过所有连续相等的元素，再执行++left。
第三个位置：匹配成功后的右指针去重。
while (left < right && nums[right] == nums[right - 1]) --right;逻辑和左指针完全对称，先跳过右侧连续相等元素，再执行--right。
这三处去重的顺序很重要。有人会把去重写在sum == 0判断之前，或者写在判断之外的其他位置，都会有漏网和错杀的问题。我习惯的顺序是：外层去重在前，内层匹配成功后再去重，这样代码读起来最顺，也最不容易错。
3.3 两处剪枝：提前退出，省下无谓扫描
第一处剪枝是if (nums[i] > 0) break;。因为数组已经排序，如果主元素本身都大于0，那它右侧的数只会更大，三数之和绝对不可能等于0。这行代码的作用不是优化正确性，而是优化速度。很多人会忽略这一点，但在n = 10000且数组全是正数的数据集里，这行代码会让循环直接退出,省下几千万次毫无意义的判断。
第二处剪枝在循环边界上：
for (int i = 0; i < n - 2; ++i) { ... }主元素只能走到倒数第三位，因为后面至少还要留两个位置给左右指针。写成i < n虽然不会报错，但最后一次循环里left会超出right，逻辑虽然还能靠while (left < right)兜底，但代码意图就变模糊了。边界写得精确，后面读代码的人一眼就能理解你的思路。
3.4 为什么不用哈希表？一个简单的对比
我也看到有人问，能不能用两数之和的哈希表思路来解三数之和。可以，做法是：外层固定i，内层用哈希表缓存-nums[i] - nums[j]是否出现过，匹配成功就记录。但问题在于去重。
哈希表只能告诉你“某个值是否存在”，不能告诉你“这个值来自哪个位置”，更没办法优雅地应付[-1, 0, 1, -1, 0, 1]这种本身含有重复值的输入。你要么把找到的元组排序后塞进集合去重，要么在遍历时额外维护大量状态。代码写起来绕，面试时还容易在边界问题上卡壳。
双指针用排序引入了“顺序信息”，去重也就变成“跳过相同元素”这一件简单事。两相对比，双指针在本题里的优势非常直观。
4. 我在调试中反复踩过的四类坑
4.1 超时：暴力解法通过了所有示例，却败给大数据集
我的第一版三数之和用的是纯暴力三重循环，本地小数组测试一切正常，示例全过，自我感觉良好。提交之后才发现，大数据集上直接超时。
当时排查思路很简单：先把数组长度打出来，再把内层循环的执行次数打印出来，一看数量级就明白了。暴力循环不会错，它就是慢，慢到你连优化提示都不用看，就知道必须降复杂度。
这里给你一个经验判断法：如果提交后极端数据下运行时间超过1秒，先看复杂度是否还在O(n^3)。如果是，别急着微调代码，直接换思路。
4.2 重复三元组：去重位置写错导致的结果翻倍
有一次我把内层去重写在了sum == 0判断之前，结果数组里只要有两个连续相同的数，匹配到目标值时就会把重复组合重复输出。
比如数组[-1, -1, 0, 1]，主元素是第一个-1时，左指针在第二个-1，右指针在1，得到[-1, -1, 1]。这是正确答案。但如果你在进入sum == 0之前就把连续相等的元素跳过了，那这个组合会被直接跳掉，输出结果里就丢了一组解。反过来，如果你在sum == 0之后不去重，那当左指针移动一步后，左指针还是-1，右指针还是1，又输出一遍同样组合。
这个坑让我领悟了一条去重原则：只有确认匹配成功后再关心“下一个是否相同”，匹配成功前绝不去动跳过逻辑。简单说就是“先取证，再排除”。
4.3 死循环与指针越界：while循环条件没写对的典型症状
一个很隐蔽的坑是while内层循环的进入条件和移动步长的不匹配。如果你只写了while (left < right)但内部某条分支没有移动指针，比如当sum < 0时忘记left++，那循环就会原地打转，直接死循环。
另一个问题是去重循环里没加left < right条件，比如：
while (nums[left] == nums[left + 1]) ++left;如果这个数组恰好是[0, 0, 0]这种全相等的数组，左指针会一路向右越界，访问到数组外的内存。这个问题在C++里表现为段错误，在Python里表现为IndexError，但根因都是同一个：当你跳过连续相等元素时，必须同时保证指针不越界。
提示：
while (left < right && ...)这个写法里，判断顺序很重要。先判断left < right，再判断元素值是否相等，短路求值能保证你不会访问非法下标。
4.4 负数与溢出：你以为很简单，其实藏着两个反直觉点
第一点是主元素大于0剪枝并不代表数组里不能有负数。很多人写完if (nums[i] > 0) break;之后，遇到负数和正数混合的数组就懵了，担心这个剪枝会漏掉负数解。实际上数组经过排序后，负数都在左侧，你在遍历主元素时，前面的负数早已被处理过了，等到主元素变成正数时，右侧自然不可能再有负数来抵消了，所以这个剪枝是安全的。
第二点是整数溢出。极端场景下，如果数据里包含接近INT_MAX的大整数，三个int相加可能溢出成负数，导致sum == 0的判断结果错乱。稳妥的做法是在求和时转成long long再比较，或者提前判断候选值是否超出可处理范围。虽然多数评测数据碰不到这种极端值，但养成这个习惯没有坏处。
5. 进阶扩展：面试官真正在等的四个变形
5.1 最接近的三数之和
这是三数之和最常见的变形：给定目标值target，找出三元组，使得三数之和与target的差的绝对值最小。
思路基本一样，先排序，然后外层固定主元素，内层双指针扫描。区别在于：你不再需要在sum == 0时记录并去重，而是每次计算当前sum和target的差值，维护一个最小差值。当sum < target时left++让和变大，当sum > target时right--让和变小。
这个变形考察的是你能不能把双指针的“方向感”迁移到“目标值不再固定为0”的场景里。代码骨架几乎没有变化，变的是比较逻辑。
5.2 三数之和小于目标值，并统计个数
第二个高频变形是：给出target，统计三数之和严格小于target的三元组个数。
这时候不去重也能做，但统计逻辑变了。排序后，外层固定i，内层同样是双指针。一旦发现nums[i] + nums[left] + nums[right] < target，由于数组有序，left和right之间的任意一个数作为第三个元素，组合出来的和都必然小于target。所以可以直接加上right - left个组合，然后left++；否则就right--。
这个变形的核心洞察是：某一组条件成立时，中间所有元素也必然成立，要不要逐一枚举。这种“批量计数”的思路，比逐个枚举更高效，也是双指针题里非常经典的技巧。
5.3 四数之和与 n 数之和的通法
四数之和的思路是：外层固定一个数，内部再固定一个数，然后剩下的两个数继续用双指针。两层for循环加一层while，时间复杂度O(n^3)。
套用这个规律可以发现：n数之和的通法就是嵌套n-2层for循环固定前n-2个数，最后两位数用双指针收缩。复杂度是O(n^(k-1))。这个通式能让你在面对四数、五数之和时快速定位复杂度瓶颈，也能帮你在递归解法和迭代解法之间做权衡。
递归解法实现n数之和的优势是代码短，劣势是去重逻辑复杂度会随着嵌套深度指数上升。我实际写下来，还是迭代嵌套更可控。
5.4 不允许修改数组的变体：哈希表的替代思路
有些变体会限制排序，比如“不允许修改原数组，且只能用常数额外空间”，那双指针就退场了。这时哈希表能派上用场：外层固定主元素，内层遍历时用哈希表缓存已经见过的元素，当发现nums[j] == -nums[i] - nums[k]时，记录组合。代价是空间复杂度升到O(n)，且重复组合的处理非常繁琐。
这类变体的意义在于帮你理解一件事：算法优化本质上是在时间、空间、数据修改权限之间做权衡。双指针适合“允许排序”的场景；哈希表适合“不能排序但可以牺牲空间”的场景；暴力循环适合“数据规模极小”的场景。没有万能解，只有约束条件下的当前最优解。
6. 一点个人体会
我后来把三数之和这道题当作一个“检验项”来做：每次刷完这道题，我都会反省自己刚才那些判断——是先分析复杂度再动手，还是条件反射般套模板；是仔细想清楚去重的位置，还是写完了再慢慢试边界。多来几次，写代码的节奏和信心真会不一样。
如果让我给你一条具体的建议：别急着背代码，先花十分钟推演一遍“排序后，双指针移动时，为什么左指针加右指针的和与目标值的差值能直接决定移动方向”。想通这一层，三数之和和它的一堆变形题，你基本就能举一反三了。面试时哪怕一下子没写全细节，能把这个推演过程讲清楚，也远比背一个答案更能让面试官信服。
这道题适合做模板，但不适合做天花板。把它吃透，接下来面对四数之和、n数之和这类扩展题时，你会发现思维方式是同一套，只是嵌套层数变了而已。
