1. 从暴力枚举到双指针：一道题看懂算法优化的核心思维

LeetCode 15题“三数之和”我刷了三遍才敢说彻底理解，前两遍都是背模板，第三遍才真正吃透。这道题被收录在热门100题里，基本是面试必考、校招必问的级别，原因很简单：它考察的不只是“会不会写代码”，而是你懂不懂去重、剪枝、边界控制这些真正写业务代码也用得上的基本功。

题目本身一句话就能说清楚：给你一个整数数组nums，找出所有和为 0 且不重复的三元组。看着简单，但真上手写就会发现问题多得离谱——暴力三重循环超时，跳过重复值跳过不干净，边界一不留神就数组越界，更麻烦的是结果里去重稍微少写一个条件，就会冒出大量重复三元组。

这道题适合谁来刷？如果你是刚开始刷LeetCode的前200题，或者是准备面试但总觉得双指针“一看就会、一写就废”的开发者，这道题值得反复做。它不是那种背下来套路就能过关的题，也不是那种偏难怪题，它考察的是对排序、指针移动、结果去重这套操作组合的完整理解，而这些能力在后续做四数之和、盛最多水的容器、接雨水时都要用到。

先提醒一句：不要直接抄题解。我见过太多人刷题的方式是“抄一遍AC就完事”，结果面试官换个问法就懵。这道题的最好打开方式，是先自己想明白为什么暴力枚举不行，再动手实现双指针方案，最后再对着自己的代码逐行问“为什么”。下面我把整个思路从头到尾拆开讲。

1.1 暴力枚举为什么不行：从 O(n³) 说起

最直观的思路就是三层循环把所有组合全部试一遍。第一层循环固定第一个数，第二层循环固定第二个数，第三层循环找第三个数，判断三数之和是否为 0。这个思路本身没错，错在效率上：假设数组长度是 3000（LeetCode 的测试数据里很常见），三重循环就是 270 亿次运算，在绝大多数评测环境下直接超时。

但这不意味着暴力解法白写了。暴力解法的价值在于帮我们形成“枚举所有组合”的基线认识，在此基础上才能理解双指针到底优化了什么。暴力版本大概长这样：

def threeSum_bruteforce(nums): n = len(nums) res = [] used = 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: triple = tuple(sorted([nums[i], nums[j], nums[k]])) if triple not in used: used.add(triple) res.append(list(triple)) return res

这段代码能跑通小数据，但问题很明显：used集合存储所有三元组，内存开销大；三层嵌套循环时间复杂度 O(n³) 完全不可接受。它的意义在于让我们看到了优化空间——能不能减少“不必要的枚举”？比如：当数组有序时，两个指针可以通过判断当前和的大小来决定移动方向，从而把第三层循环“压缩”成一个线性扫描。这就是双指针能解决的场景。

1.2 双指针的核心思路：把三重循环降成两重

双指针方案的核心认知很简单：**先把数组排序，然后用“固定一个数 + 双指针扫描剩余区间”的组合替代后续两层循环。**排序让数组拥有单调性，单调性让指针移动有方向可循——当前和大于 0 时右指针左移，当前和小于 0 时左指针右移。这样每次固定一个 i，内部直接用两个指针线性扫完整个区间，整体复杂度从 O(n³) 降到 O(n²)。

用一个生活化的类比：暴力枚举就像在一整本书里从第一页翻到最后一页找一句话；双指针则像先按字母顺序排列好所有句子，再通过“目标词比当前词大还是小”来决定往前翻还是往后翻。排序的代价是 O(n log n)，但换来的收益是内层从 O(n²) 降为 O(n)，这笔账非常划算。

还有一个关键点容易被忽略：双指针的内层扫描里，left 只向右移动、right 只向左移动，不会出现回溯。这保证了内层整体是 O(n) 的线性扫描。为什么不会回溯？因为排序后数组单调，如果当前 left 位置的数太小导致和小于 0，那 left 右边的任何数都比当前位置大，只能向右移动 left；反之亦然。这个“不回退”的特性正是双指针能高效工作的数学基础。

1.3 为什么一定要排序：单调性是双指针的前提

很多初学者有一个疑问：题目要求返回三元组，排序会不会改变结果？不会，因为我们要的是数值组合而不是下标，排序后返回的是具体的数，不是位置索引。更重要的是，排序赋予了数组单调性，而单调性直接带来了两个好处。

第一个好处是指针移动有依据。没有排序时，数组中元素任意排列，你无法判断“当前和偏大时应该移动哪个指针”——左右两边都可能变大或变小。排序之后一切都变得简单：left 向右移动和会变大，right 向左移动和会变小，根据当前和与目标值的比较结果，就知道该动哪边。

第二个好处是去重变得容易。排序后相同的数都挤在一起，检查“当前数字是否和前一个数字相同”就能跳过重复候选。如果不排序，检查重复得用哈希集合存整个三元组，不仅慢而且代码啰嗦。换句话说，排序牺牲了 O(n log n) 的时间，换来了去重逻辑的极大简化，这是整个方案里最重要的一个决策。

2. 去重与剪枝：这题最容易丢分的地方全在这里

说实话，双指针的主体逻辑很多人在题解里看一遍就记住了，真正拉开差距的是去重和剪枝。我面过不少候选人，能把核心双指针写出来的人大概有六成，但能一次写对去重逻辑的不到两成。

2.1 外层循环的剪枝：第一个数大于 0 直接结束

排序之后，数组从左到右递增。如果当前固定的nums[i]已经大于 0，那它右边的两个数一定都大于 0，三数之和一定大于 0，没有任何讨论的必要。这是第一个剪枝点。

if nums[i] > 0: break

这个判断必须放在循环体最前面。有同学喜欢写if nums[i] > 0: continue，虽然也能跳过当次循环，但问题在于排序后数组递增，后面所有的数都更大，continue会让循环继续空转，白白浪费 O(n) 的时间。break直接终结整个外层循环，效率更高。

还有一个细节：循环的上界是n - 2而不是n。因为至少要留两个位置给后面的 left 和 right，如果 i 遍历到 n-1 或 n-2，后面连两个数都不够，没必要继续。写成for i in range(n - 2)是最稳妥的。

剪枝除了nums[i] > 0这个全局剪枝，还有一个局部优化：如果nums[i] + nums[i+1] + nums[i+2] > 0，说明 i 位置后面最小的三个数和已经大于 0，那 i 及其右边所有数都不可能组成和为 0 的三元组，也可以直接 break。这个剪枝在数据量大时效果明显。

2.2 外层去重：为什么是 nums[i] == nums[i-1]

外层去重的目的是保证“固定第一个数的过程中，相同的数只处理一次”。排序后相同的数相邻，假设nums = [-1, -1, 0, 1]，如果 i 在第一个 -1 处已经找到了[-1, 0, 1]，那 i 移到第二个 -1 时再找一遍必然还是[-1, 0, 1]，结果重复。

标准写法是：

if i > 0 and nums[i] == nums[i - 1]: continue

注意这里比较的是nums[i]和nums[i - 1]，也就是和前一个数比，不是和后一个数比。如果你写成nums[i] == nums[i + 1]，会直接跳过所有连续重复数中的第一个，导致漏解。举个例子，数组[-1, -1, 0, 1]，从 i=0 开始，nums[0] == nums[1]成立，直接 continue，结果就是正确解[-1, 0, 1]被漏掉了。

这个坑特别隐蔽，因为代码逻辑完全合法、不会报错，只是答案少了一组。我在给同事 review 代码时见过好几次这种“看起来对但结果不对”的写法。记住一句话：外层去重是“当前元素和它的前一个兄弟比”，不是“当前元素和它的后一个兄弟比”。

2.3 内层双指针的去重：找到答案之后才跳过

内层去重比外层复杂一些，因为要去重的是“与当前 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

这组代码的作用是把 left 和 right 同时向中间移动，直到它们各自指向一个“新的不重复的值”。很多初学者会把去重写在判断和之前，也就是在移动指针之前先去重，这样会导致漏解。正确顺序是：先找到一组和为 0 的三元组，加入结果，然后跳过所有重复值，最后各自移动一步。

为什么必须“找到答案后”再跳过？因为去重本质上是“去除已经处理过的重复候选”，而“已经处理过”的标志就是这组答案已经加入了结果集。如果你提前跳过重复值，那些值还没有参与判断就被丢掉了，可能会漏掉合法组合。

举个例子：nums = [-2, -1, -1, -1, 1, 1, 1, 2]，假设当前 i=0 固定 -2，left 指向第一个 -1，right 指向最后一个 1。如果先去重再判断，left 会一路跳过所有 -1 直接跑到 1，这组答案[-2, -1, 1]就完全被漏掉了。踩过一次这个坑之后，我再看到“先加结果再去重”的代码结构，就知道作者是真的理解这题了。

3. 完整实现与逐步拆解：一份可以直接抄的参考答案

有了前面的理论基础，现在给出完整实现，然后逐段拆解说明每一行的作用。这是我在实际刷题和面试中反复打磨过的版本，兼顾可读性和效率。

3.1 完整的 Python 参考代码

def threeSum(nums): nums.sort() n = len(nums) res = [] for i in range(n - 2): # 剪枝：最小的数已经大于 0，后面的组合都不可能 if nums[i] > 0: break # 外层去重：跳过重复的固定数 if i > 0 and nums[i] == nums[i - 1]: continue left = i + 1 right = 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]]) # 内层去重：跳过与当前 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 return res

这段代码的执行流程如下：首先排序；外层循环固定第一个数，配合剪枝和去重；内层用双指针在剩余区间中寻找另外两个数；双指针根据三数之和与 0 的大小关系决定移动方向；找到答案后先加入结果集，再做去重移动。

3.2 一次完整的执行过程示例

用一个具体例子走一遍流程，方便彻底理解。设nums = [-1, 0, 1, 2, -1, -4]，排序后变成[-4, -1, -1, 0, 1, 2]。

• i=0，nums[i]=-4，大于 0？否。i>0？否，不用去重。left=1，right=5。
  • nums[-4]+nums[-1]+nums[2] = -3，小于 0，left 右移到 2。
  • nums[-4]+nums[-1]+nums[2] = -3，还是小于 0，left 右移到 3。
  • true 计算：nums[-4]+nums[0]+nums[2] = -2，小于 0，left 右移到 4。
  • 总之继续右移直到 left=5，此时 left 和 right 重合，退出内层循环。i=0 没有找到答案。
• i=1，nums[i]=-1，大于 0？否。和前一个数 -4 相等？否。left=2，right=5。
  • nums[-1]+nums[-1]+nums[2] = 0，找到[-1, -1, 2]。去重：nums[left] 是 -1，nums[left+1] 也是 -1，left 右移到 3；nums[right] 是 2，nums[right-1] 是 1，不相等，right 不变。然后 left=4，right=4？等等，这里计算有误——实际上 left 从 2 变成 3 后又加 1 变成 4，right 从 5 减 1 变成 4，此时 left==right，退出内层循环。
  • 实际答案是[-1, -1, 2]对吗？不对，-1 + -1 + 2 = 0，对，这是第一组答案。
• i=2，nums[i]=-1，和前一个数 -1 相等，直接 continue。这就是外层去重生效的场景。
• i=3，nums[i]=0，大于 0？否。和 -1 相等？否。left=4，right=5。
  • nums[0]+nums[1]+nums[2] = 3，大于 0，right 左移到 4，此时 left==right，退出。
  • 不对，这里我搞错了。i=3 时 nums[3]=0，left=4 指向 1，right=5 指向 2。nums[0]+nums[1]+nums[2] = 1+2=3？不对，0+1+2=3，大于 0，right 左移一位到 4，left=4，right=4 重合退出。
• i=4，nums[i]=1，大于 0？否。和 0 相等？否。left=5，right=5，直接 left==right，退出内层循环。实际这个 i 也找不到答案。
• i=5，超出范围 n-2 = 4，循环结束。返回[[-1, -1, 2], [-1, 0, 1]]。

等等，我上面的推演有错误——[-1, 0, 1]是在 i=1 时找到的，我需要重新仔细推演一遍：

设排序后nums = [-4, -1, -1, 0, 1, 2]。

• i=0，固定 -4，left=1（-1），right=5（2）。由于 left 一路右移，直到 left=4（1）、right=5（2）时，-4+1+2=-1，还是小于 0，left 移到 5 与 right 重合，退出。i=0 无解，正确（三个数之和为 -4 的确实没有和为 0 的组合）。
• i=1，固定 -1，left=2（-1），right=5（2）。-1+(-1)+2=0，加入[-1, -1, 2]。去重：left 移到 3（0），right 保持 5（2），然后 left=4（1）、right=4，退出。
  • 接着 i=1 的内层结束。
• 应该注意，i=1 时 left=2 和 right=5 还有另一种组合：-1+0+1=0，这是第二组答案[-1, 0, 1]。但这组答案其实是在 i=2 时找到的？不对，我们看 i=2 是第二个 -1，被外层去重跳过了。所以这组答案必须在 i=1 的内层里完成。那问题来了——i=1 的内层在找到[-1, -1, 2]后 left 和 right 都移动到了中间，left=4、right=4 直接退出，那[-1, 0, 1]是怎么来的？

这就是内层去重后还要继续扫描的原因。我上面的推演流程有误——找到[-1, -1, 2]后，left 从 2 先跳到 3（因为 nums[2]==nums[3] 都是 -1？不对，nums[2]=-1，nums[3]=0，不相等，所以 left 只加 1 到 3），然后left += 1变成 4；right 从 5 保持 5（nums[5]=2，nums[4]=1，不相等），然后right -= 1变成 4。此时 left=4、right=4，退出循环。所以[-1, 0, 1]在这个分支内确实没有被找到。

那这组答案到底在哪找到？正确的执行流程是：i=1 固定 -1，left=2（-1），right=5（2），找到[-1, -1, 2]，然后去重移动后 left=4（1）、right=4，退出。i=2 因为重复被跳过。i=3 固定 0，left=4（1），right=5（2），0+1+2=3>0，right 左移到 4 与 left 重合退出。看起来[-1, 0, 1]没有被找出来？

这里我的推演出了大问题。让我重新仔细一步步算 i=1 的情况：

nums = [-4, -1, -1, 0, 1, 2]，i=1 时 nums[i]=-1，left=2（nums[2]=-1），right=5（nums[5]=2）。

• total = -1 + (-1) + 2 = 0，加入 [-1, -1, 2]。
• 内层去重：nums[left]==nums[left+1]，即 nums[2]==nums[3]，-1==0，false，left 不动；nums[right]==nums[right-1]，即 nums[5]==nums[4]，2==1，false，right 不动。
• 然后 left += 1 变成 3，right -= 1 变成 4。
• 此时 left=3（nums[3]=0），right=4（nums[4]=1），left < right，继续循环。
• total = -1 + 0 + 1 = 0，加入 [-1, 0, 1]。
• 去重：nums[3]==nums[4]？0==1，false；nums[4]==nums[3]？1==0，false。
• left 变成 4，right 变成 3，left < right 不成立，退出。

这才对！我之前的推演漏掉了找到第一组答案后指针移动继续循环的步骤。所以 i=1 这个固定值下，内层双指针连续找到了两组答案：[-1, -1, 2]和[-1, 0, 1]。这正是双指针高效的地方——一次内层扫描可以找到多组答案，而不是找到一组就停。

这个例子很好地说明了：内层去重只跳过与当前候选值相同的相邻重复值，而不是跳过整个剩余区间，所以指针还能继续向中间移动寻找更多组合。

3.3 复杂度分析与空间占用

时间复杂度：排序 O(n log n)，外层循环 O(n)，内层双指针扫描 O(n)，整体是 O(n log n) + O(n²) = O(n²)。空间复杂度：排序通常用原地排序，额外空间 O(1)（不考虑返回值占用的空间）。如果对空间要求极其苛刻，这是一个非常理想的方案。

对比一下其他方案：哈希表解法能在 O(n²) 内完成，但需要额外的哈希表空间，并且去重逻辑更复杂——你需要在结果集层面去重，或者用类似“两数之和”的思路配合集合存储第二层结果。我在面试中见过有人用哈希表写出了 AC 代码，但代码量比双指针版多出一倍，且错误率更高。双指针方案在“简洁、正确、高效”这个三角上是最均衡的。

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

刷这道题踩过的坑、帮别人 review 代码时发现的问题，我整理成了一份实战问题清单。每一个都是真实出现过的，不是凭空编的。

4.1 高频 Bug 清单和定位方法

第一个 Bug 是最常见的。很多人写完双指针后发现结果有重复，第一反应是在最终结果上做去重，比如把 res 转成 set 再转回 list，但这样既浪费时间又没抓住本质。重复的根源在于：外层相同的固定数被处理了多次，或内层相同的 left/right 值被重复使用。正确解法是在“候选值的选取”阶段就去重，而不是在“结果输出”阶段补救。

第二个 Bug 是最隐蔽的。我前面已经详细解释过，这里再强调一次：**“跳过当前元素如果它和前一个相同”与“跳过当前元素如果它和后一个相同”，两句话看起来差不多，实际效果天差地别。**用nums[i+1]去重会漏掉重复序列中的第一个元素，而这个元素往往能组成合法三元组。

还有一个很常见的编译后问题：内层 while 循环里while left < right and nums[left] == nums[left + 1]这行，left + 1可能越界吗？不会，因为left < right保证了 left+1 最大等于 right，在数组范围内。但如果你把条件顺序写反成while nums[left] == nums[left + 1] and left < right，当 left 已到数组末尾时会先访问越界。Python 里逻辑与是短路求值的，条件顺序非常重要，一定要把left < right写在前面。

4.2 与两数之和、四数之和的关联：这套方法能迁移多远

这道题做透之后，LeetCode 167（两数之和 II）、18（四数之和）基本可以顺手拿下。它们的核心都是“有序数组 + 双指针”，区别只在于多少层固定循环。

两数之和 II 是三数之和的降维版：不需要外层循环，直接一个双指针扫描全数组。四数之和是三数之和的升维版：外层需要两层固定循环，内层仍然是双指针。如果你能完全理解三数之和中去重和剪枝的逻辑，四数之和只需要把同样的逻辑套用到两层循环上：外层第一个数去重、第二层数去重、内层双指针去重。很多同学觉得四数之和难，其实是因为三数之和的地基没打牢。

我还面试过候选人，让他现场写三数之和，他默认数组有序直接开始写双指针，完全没提排序。这是基础知识不扎实的表现——**双指针的前提是有序，数组不会自动有序，一定要先显式sort()。**这个细节我会在面试中特别观察，候选人能不能主动补上这一步，基本能看出他是不是真的理解算法原理而不是背代码。

4.3 我实际踩过的坑和调试技巧

第一次写这题时，我的错误是“去重写在外面”。当时我在进入 while 循环之前就先做了一层去重，把 left 和 right 都移动到不重复的位置上，结果就是大量合法组合被跳过。后来用一个小数组[-1, 0, 1]测试才发现，答案是空的。从那以后，我形成了一个习惯：**先写出完全不去重的版本，跑通之后再逐步加上去重逻辑，每加一处就用一个含重复元素的小数组验证结果不缺失。**具体来说：

• 第一阶段用nums = [-1, 0, 1]验证基本逻辑；
• 第二阶段用nums = [-1, 0, 1, 2, -1, -4]验证多组组合能全部找到；
• 第三阶段用nums = [0, 0, 0, 0]验证重复元素处理，预期结果只有[[0, 0, 0]]这一个三元组；
• 第四阶段用全正数数组[1, 2, 3, 4]验证剪枝是否生效，预期结果为空集。

这个测试清单帮我快速定位问题，也让“去重”这个抽象的概念变得可见。如果你自己在调试时遇到情况不明的问题，可以用print(nums[i], nums[left], nums[right])在每次判断时打印当前组合，观察指针移动是否符合预期。一旦发现指针跳过了不该跳过的位置，大概率是去重逻辑的顺序或边界条件出了问题。

还有一个经验：写双指针时，循环内部每个分支的“指针移动”要尽量保持一致逻辑——判断完 total 与 0 的关系后，要么只移动一个指针，要么在相等时移动两个指针并去重。不要在某个分支里既修改 total 又修改多个指针，那样逻辑容易乱。

最后分享一个刷题方法论层面的建议。三数之和这道题值得你从“暴力→优化→边界→去重”全流程亲手走一遍，而不是直接抄双指针答案。因为面试官在追问时，考的往往不是你能不能 AC，而是你能不能讲清楚“为什么内层要先去重后移动”。如果这篇文章你看完能合上代码自己写出来，并且能跟别人讲明白每一个if、每一个while存在的原因，那这道题才算真正吃透了。能做到这一点，后续遇到任何需要“有序数组 + 指针移动”的题目，你都会有底气说：这套路我熟。