企业官网建设流程全解析

1. 三数之和到底是一道什么样的题

算法梳理这个系列写到这里已经是第四篇，今天要聊的是经典算法题库里的第15题：三数之和。在算法面试和工程思维训练里，“三数之和”四个字基本是数组题目的分水岭。很多人刷题是从“两数之和”起步的，觉得顺着思路扩展到三数不就多一层循环吗？真正上手才发现，问题不在“找三个数”，而在“不重复”这三个字。

1.1 题目本身只提了一个要求

题目非常直白：给定一个包含 n 个整数的数组 nums，判断是否存在三个元素 a、b、c，使得 a + b + c = 0，并找出所有满足条件且不重复的三元组。比如数组是 [-1, 0, 1, 2, -1, -4]，答案有两个：[-1, -1, 2] 和 [-1, 0, 1]。

这里有个反直觉的点：-1 在数组里出现了两次，但结果里不能出现两个 [-1, 0, 1]。“不重复”指的是三元组整体不能一样，而不是每个位置的数字不能重复。同一个数值在一组答案里出现两次完全可以，比如 [-1, -1, 2]，只要它在数组里有足够的数量支撑。

1.2 为什么它在算法题典里地位特殊

我面试过不少开发候选人，这道题能快速说出思路的人很多，但代码能一遍跑对、并且把去重逻辑讲清楚的非常少。原因在于，这道题表面上考的是穷举，实际上考的是三个能力：能不能想到用排序创造有序条件，能不能在 O(n²) 里完成搜索，以及能不能把边界条件、去重条件考虑完整。

这也解释了为什么各大刷题平台要把三数之和放在第15题这个位置，前面是简单的两数之和，后面紧接着是最接近的三数之和、四数之和。它起到的是承上启下的枢纽作用。如果你能彻底吃透这道题，后面的四数之和基本就是套模板的事。

1.3 谁需要认真吃透这道题

这篇内容适合两类人。一类是把算法当工具、平时写业务代码的开发者，想搞懂这套“固定一个数，双指针扫剩下的区间”的套路，以后遇到组合约束类问题能想到用它。另一类是准备技术面试的人，需要把这道题连同变种题一次吃透，做到面试时能写出无 bug 的答案。

我会从暴力解讲起，再拆排序加双指针的最优解，最后把去重细节、常见 Bug、以及怎么推广到 n 数之和都展开讲。每个结论我都会解释为什么这么做，而不只是甩一段代码。

2. 暴力三重循环：思路最直，死在去重上

2.1 第一版代码长什么样

先看最简单的想法：三数之和等于 0，那我把所有三个数的组合都算一遍，遇到和为 0 就记录下来，这不就完了？

如果完全不考虑时间复杂度，代码是这样的：

def threeSum_brute(nums): 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: tri = sorted([nums[i], nums[j], nums[k]]) if tri not in res: res.append(tri) return res

这段代码逻辑完全正确。而且我加了一行 sorted(...)，把三元组内部排好序，再通过 tri not in res 去重。但是这里藏着两个致命的问题。

第一个问题是性能。三重循环的次数是组合数 C(n, 3)，当 n = 3000 时，大约是 45 亿次组合计算。哪怕每次只做一次加法，在普通机器上也要跑几十秒甚至几分钟。而现实里接口入参的数组动辄上万，完全没法用。

第二个问题是去重办法太粗糙。每次找到一组答案都要遍历一遍 res 列表，判断是否已经存在。res 越大，这个判断越慢。最坏情况下，整体复杂度比 O(n³) 还要高出一个常数倍，属于多重暴击。

2.2 去重问题的真相

暴力解法的去重，依赖的是“排序后比较整个三元组”。这意味着我们要承担排序每个候选三元组的成本，还要承担线性查找结果列表的成本。这其实不是最优方案，但它暴露了这道题的核心难点：数值有重复，组合无顺序。

比如数组 [0, 0, 0, 0]，你需要找所有和为 0 的三元组。暴力法会枚举出很多个 [0, 0, 0]，最终通过去重只保留一个。问题在于，怎么样用最低的成本做到这一点。

如果数组是无序的，去重真的只能靠“看集合里有没有”这种笨办法。但如果数组是有序的，比如 [0, 0, 0, 0]，三个 0 是相邻的，我们扫描时就知道：同样的值，跳过后面重复的即可。这就是一个关键转折点——去重问题的本质是，你要在“枚举过程中”去重，而不是在“枚举结束后”去重。

简单的数学观察也能帮助理解：如果三个数 a + b + c = 0，且这三个数按大小排序，那么每个三元组都有唯一的升序形态：a ≤ b ≤ c。只要能保证枚举到的 a、b、c 是升序的，就天然去掉了排列带来的重复。

2.3 复杂度账本看一眼

把暴力解的复杂度量化一下可能更直观。假设 n = 1000：

• 循环次数：C(1000, 3) ≈ 1.66 亿次
• 每次进制要做一次排序来规整三元组，常数更高
• 还要在 res 里做线性判重，结果越多越慢

不是不能跑，是这种写法在你真的跑起来的时候，会跑出一种“莫名其妙卡住”的绝望感。而排序加双指针的解法，在 n = 1000 时大约只需要执行 50 万次左右的加法和比较运算，两者差了三百倍以上。这就是为什么面试官看到暴力解，通常不会往下听。

当然，暴力解不是一无是处。它的价值在于验证思路：当 n 很小的时候，它是最不容易写错的版本，可以用作参考答案来验证更优解的正确性。我在本地自测最优解时，就会写一个暴力版做对拍——随机生成数组，比较两个版本的输出是否完全一致。这个技巧后面会细说。

3. 排序加双指针：最优解的核心思路

3.1 排序给问题带来了什么

很多人看到最优解的第一步是 nums.sort()，会觉得很玄学，明明题目没有要求排序。但排序带来两个关键收益。

第一，让重复值变成连续块。数组有序后，相同的数字挨在一起，我们扫描到重复值时可以直接跳过，去重从“事后查重”变成了“事前跳重”。这件事的意义，比很多人想象中大得多。

第二，让“区间内找两个数等于某个目标值”变成线性问题。假设我们固定了第一个数 a，那么问题变成：在 a 右边的有序区间里，找两个数 b、c 使得 b + c = -a。对这个有序区间，双指针从两端往中间逼近，一次遍历就能完成搜索，不需要嵌套循环。

这里有个逻辑需要强调：排序并没有改变原题的结果集，因为三元组是否和为 0、是否总体重复，只跟元素的数值和数量有关，与它们在数组里的位置无关。所以排序是安全操作。

3.2 双指针收敛的数学直觉

两数之和等于目标值 target，在一个有序数组里用双指针找，这个子问题本身就是经典。左指针 left 指向区间起点，右指针 right 指向区间终点，计算 current = nums[left] + nums[right]。

如果 current 小于 target，说明当前左指针位置的数太小，需要往右移，让和变大一点；如果 current 大于 target，说明右指针位置的数太大，需要往左移，让和变小一点；如果相等，那就记录答案，并且两个指针同时向内收缩。整个过程每个元素最多被访问一次，复杂度 O(n)。

这个收敛过程背后是数学直觉：有序区间里，left 往右移动时，和单调递增；right 往左移动时，和单调递减。两个指针一进一退，相当于把二维搜索空间压成一条单次扫描的路径，而不是一个嵌套平面。这就是双指针算法高效的核心原因。

把三数之和套到这个子问题上：外层循环枚举第一个数 a，内层把剩下的区间交给双指针找 -a。外层要跑 n-2 次，内层每次 O(n)，总复杂度 O(n²)。排序是 O(n log n)，在大 O 层面被忽略，所以三数之和的最优时间复杂度就是 O(n²)。

三种思路的对比可以看这张表：

3.3 去重的三个关键位置

双指针方案里，去重需要写在三个地方，少了任何一个都可能漏。按代码执行顺序讲：

第一处，外层固定 a 时。如果 nums[i] == nums[i-1]，说明当前 a 的值和上一次相同。对同一个 a，双指针扫出来的结果是完全一样的，这次循环可以直接跳过。这里要注意是 i > 0 时比较 nums[i] 和 nums[i-1]，而不是 nums[i] 和 nums[i+1]，因为后者会漏掉第一个出现的值。

第二处，双指针找到一组答案后。记录完 [a, b, c]，如果下一个 left 指向的值仍然等于 b，那以相同的 b 再去搜索，只会得到重复三元组，所以 left 要一直右移跳过重复值；同理，右侧也要左移跳过重复的 c。

第三处，也是最容易被忽略的：在没找到答案时，移动指针不必去重。因为目标值不同，即使值重复，指针也要一步一步挪；强行跳重复反而可能错过中间的状态。很多初学者会在 total < 0 时写 while 跳过重复值的代码，看起来合理，实际上这样优化收益有限，还容易引入边界错误。

这三处去重的共同原则是：只在可能产生重复答案的瞬间去重，不要在探索路径时提前去重。理解这个原则，比背代码重要得多。

4. 可运行的完整实现与逐行解读

4.1 Python 参考实现

把思路落地成代码，下面是我在实际写题和工程参考里都会采用的标准写法：

def threeSum(nums): res = [] n = len(nums) if n < 3: return res nums.sort() 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: res.append([nums[i], nums[left], nums[right]]) # 找到答案后，跳过重复的 left 和 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

这段代码有几个细节值得反复看。

第一个细节是外层循环的长度是 n-2，因为至少要给 left 和 right 留位置。如果 n 小于 3，直接返回空。

第二个细节是 nums[i] > 0 时直接 break，而不是 continue。因为数组已经升序排序，i 位置是剩下数里最小的，如果它都大于 0，之后所有数都大于 0，三个正数不可能和为 0。这个剪枝虽然不影响复杂度的大 O，但实测在全是正数的数组里，能省掉几乎全部循环。

第三个细节是找到答案后，先跳重复再统一移动一次指针。这样写的好处是逻辑对称，不容易出错。不少版本是先 left += 1 和 right -= 1，再跳重复，效果一样，但我推荐先跳后移，因为在 while 条件里借用 left < right 做边界保护更顺手。

4.2 Java 版本与语言差异

同样的逻辑用 Java 写，流程完全一致：

public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; if (n < 3) { return res; } Arrays.sort(nums); 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; int right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { res.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 res; }

语言层面的差异主要在两个地方。一是 Java 的 List<List > 泛型嵌套，不少初学者会在这里写错；二是 int 溢出问题，数组里如果存在很大整数，理论上 sum 可能溢出，所以有的工程写法会强转成 long 再求和，或者提前判断范围。Python 没有这个担忧，但 Java 和 C++ 选手建议形成用一个 long 存和的习惯。

4.3 复杂度确认与边界用例

时间上，排序 O(n log n)，外层循环最多 n-2 次，内层双指针逼近是 O(n)，整体 O(n²)。空间上，如果不把返回结果计入，只需要排序时 O(log n) 的栈空间和常数空间，所以很多人说它是 O(1) 额外空间。

这里放两个边界用例，建议你在本地亲手跑一遍：

• nums = [0, 0, 0, 0]，期望输出一个 [0, 0, 0]。代码在 i = 0 时找到一个三元组，随后 left 跳重复越过两个 0，right 同理，最终只记录一次。
• nums = [-2, 0, 1, 1, 2]，期望输出 [-2, 0, 2] 和 [-2, 1, 1]。

第二个例子是验证去重逻辑的好用例。当 left 和 right 同时指向两个 1 时，它俩在结果里的位置有区分度，但整体却混在同一个三元组里，只有严格的指针移动逻辑才能保证不重不漏。

5. 实战中真正容易踩的坑

5.1 高频 Bug 清单

我整理一份高频出错点，每一项都是我实际见过或者自己在调试里踩过的。直接上表格，对照看更清楚：

这里最值得展开的是第二行。“和下一个比较”和“和前一个比较”的区别，很多新手看不出问题。如果我写 if nums[i] == nums[i+1] and 此时 continue，遇到 [-1, -1, 2] 时，i=0 的 -1 会被跳过，最终正确答案 [-1, -1, 2] 直接漏掉。而 if i > 0 and nums[i] == nums[i-1] 是让第一个 -1 正常参与搜索，后续重复的 -1 跳过，答案被完整保留。

5.2 一套三层递进的排错方法

我在调试这段代码时，最常用的方法可以概括成三层递进。

第一层，拿小样例手算。比如数组长度 3 的情况直接验证；长度 4 的情况遍历一遍逻辑。手算能帮你排除绝大多数思路性错误，因为三数之和的边界条件非常少，手算成本很低。

第二层，打印关键变量。在每次 while 循环开头打印 i、left、right、total 和当前 res。不用打印太多，只打印这几个变量，指针移动是否符合预期就一目了然。尤其是死循环，看打印日志能马上发现问题所在。

第三层，对拍。写一个暴力解法的版本，随机生成数组，用两个版本分别跑，比较结果集合是否完全一致。这个技巧在很多算法题里都好用。我通常用几百个随机用例对拍，一旦发现不一致，就用最小化用例定位差异。

还有一个补充习惯：测试时不要只测有答案的用例。空数组、单元素数组、全零数组、全正数组、全负数组，这些“没有答案”的用例最容易暴露边界问题。很多看起来完美的代码，在 nums 长度小于 3 时会直接越界。

5.3 两个按需加入的优化技巧

除了常规写法，还有两个能提升性能的小优化，平时可以按需加上。

第一个是数组级剪枝。排序后，如果第一个数乘以 3 大于 0，或者最后一个数乘以 3 小于 0，说明整个数组的同号情况极端，可以直接返回空，省掉整个双指针流程。

第二个是外层枚举的区间压缩。当 nums[i] 和它后面最接近的两个数之和大于 0 时，其实可以提前 break；当 nums[i] 和数组最后两个数之和仍然小于 0 时，说明当前的 i 太小，可以 continue。这类剪枝会让代码复杂不少，我的建议是只在需要压性能的场合加，日常刷题和面试保持代码可读性更重要。

提示：Python 的 sort 对纯数字列表效率很高。如果你在 Java 里用的是 int[]，Arrays.sort 用的是双轴快速排序；如果用的是 List ，会多一层装箱开销。能传数组就不要传 List。

6. 从三数之和到 n 数之和：一套思路打天下

6.1 先理解它与两数之和的关联

两数之和问题有两种主流解法：哈希表 O(n)，或者在有序数组上用双指针 O(n)。三数之和其实可以看成“固定一个数后的两数之和问题”。固定 a 之后，剩下的 b + c = -a 就是一个两数之和，而且是在有序区间内。

所以三数之和的最优解可以概括成一句话：排序，然后对每个 i，在右侧区间跑一遍双指针两数之和。这个“减少一个自由度的思路”是核心。很多人只会背代码，没意识到自己在做“降维”，遇到四数之和就懵了。

有了这个认知，四数之和就不是新题：固定第一个数，就变成三数之和；再固定第二个数，又退回两数之和。本质上是一个递归嵌套的结构。

6.2 递归版 nSum 通解

n 数之和的通用解法，是在 nums 排序后，写一个递归函数，每一层固定一个数，直到待求数量变成 2，然后用双指针收尾。我整理过一版可以直接复用的通解，大致结构是这样的：

def nSum(nums, n, target): nums.sort() res = [] def helper(start, n, target, prefix): if n < 2: return if n == 2: left, right = start, len(nums) - 1 while left < right: total = nums[left] + nums[right] if total == target: res.append(prefix + [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 < target: left += 1 else: right -= 1 return i = start while i < len(nums) - n + 1: # 剪枝：当前最小数作为平均值起点时已经过大 if nums[i] * n > target: break # 剪枝：最小数加上最大 n-1 个数都不够 if nums[i] + nums[-1] * (n - 1) < target: i += 1 continue # 每层去重 if i > start and nums[i] == nums[i - 1]: i += 1 continue helper(i + 1, n - 1, target - nums[i], prefix + [nums[i]]) i += 1 helper(0, n, target, []) return res

这个通解可以直接用于四数之和这类更进阶的题目。核心思想是每一层减少一个维度，注意每层都要做同样的去重和剪枝。我在实际面试准备里，把三数之和理解到这个通解之后，四数之和基本只需要十分钟就能写出来。通解代码里的剪枝条件不一定所有情况都必要，但值得理解，比如当前最小数 n 倍已经超过 target，后面的组合只会更大，直接断掉整层循环是安全的。

6.3 变种题与现实场景的影子

围绕三数之和，算法平台上还有不少直接变种：

• 最接近的三数之和：给定 target，找出三数之和与 target 最接近的值。双指针依然能用，每次计算差值并维护最小差即可。
• 三数之和小于 target 的个数统计：这类题求的是“个数”而不是“具体组合”，双指针配合区间计数，能把复杂度控制在 O(n²)。
• 四数之和：递归 nSum，或者两层固定加双指针，都行。

现实业务里，三数之和的思想也有应用场景。比如电商要设计“三件商品组合优惠”，要求三件商品的标价总价正好等于某个满减阈值；或者风控系统里要匹配三个规则条件的组合，使总权重落在某个区间；再比如游戏数值设计里，安排三个技能的数值配比。这些场景不会直接拿这道题的代码，但“先排序、再固定一个变量、最后双指针逼近目标”这三个步骤，是这类组合约束搜索问题非常通用的一般套路。

最后再分享一个真实经验。我曾在工作中遇到一个需求：从一批历史交易金额里找三笔，让它们的和最接近某个清算总额。数据量大约两万条，用三重循环根本跑不动。我当时把三数之和的模板改成了“最接近”的版本，O(n²) 在两分钟左右就出了结果。从那以后，我对这道题的评价就从“面试算法题”变成了“能直接变现的工程工具”。

还有一个心得：不要太早背模板。先自己画一个有序数组，在纸上模拟一遍双指针的移动轨迹，理解指针为什么一进一退，再去写代码。一旦你真正理解了指针收敛的原因，去重逻辑自然能推导出来，因为同一组答案只能从同一条路径访问到。

注意：如果题目只问“是否存在”而不是“列出所有组合”，那么双指针方案在找到第一组答案后可以直接返回，不需要扫完整个区间。这个微小的变化可以继续减半运行时间。面试时如果能说出这个小优化，通常会让面试官高看一眼。

这道题我前前后后看了不下十遍，也解答过不少朋友的各种写法问题。每次回头看，都能发现一点新的理解：最开始是背代码，后来是懂指针，再后来是彻底明白“有序数组上的枚举压缩”这个思想。如果你正在为这道题发愁，多花十分钟把指针轨迹在纸上画一遍，比多刷十道类似的题都管用。