1. 为什么大家都在“背”三数之和却还是写不对LeetCode 15题“三数之和”大概是所有刷题人绕不过去的一道题。刷过的人都能背出答案框架“排序固定一个数双指针扫去重。”但真到白板手写或者面试官追问“你这个去重为什么不去重i本身”的时候很多人就卡住了。这不是记不牢的问题而是大多数人根本没搞懂这个解法背后的推导逻辑——为什么非要排序双指针为什么能替代第三层循环三个位置的去重分别防的是什么这篇文章想做的就是把从暴力枚举到双指针的完整推导过程、去重和剪枝的具体写法、以及边界控制的每一个关键细节一次性讲透。读完你可以不用再背答案而是能在白板上现场推出解法也扛得住追问。我见过太多人刷这道题的状态AC了但换个输入样例就会写出重复结果或者干脆在“去重”这块直接摆烂用Set兜底。这样不是不行但面试官几乎一定会追问“你能不能用常数级额外空间做去重”。所以这篇的重点不只是让你过题而是让你真正理解为什么去重要写在循环的特定位置为什么跳过条件是nums[i] nums[i-1]而不是nums[i] nums[i1]为什么剪枝可以放心大胆地提前退出。这些都是拉开水平差距的细节。2. 暴力枚举不是不能用先把复杂度账算明白2.1 三重循环的数学本质假设我们把问题退回到最简单版本找出所有a b c 0的三元组先不管重复不重复。暴力解法非常直觉三重循环枚举所有下标组合i j k判断三数之和是否为零。组合数量是 C(n, 3)展开之后是 n(n-1)(n-2)/6复杂度就是 O(n^3)。当 n 3000 时组合数大约是 44.9 亿次基本运算。这在大部分在线评测系统里是跑不完的更不用说面试时“时间复杂度O(n^3)”说出口就输了半截。用数据说话更直观数组长度组合数大概需要的时间以普通机器估算100161,700毫秒级10001.66亿秒级300044.9亿分钟级100001.67万亿小时级LeetCode 的nums.length上限通常是 3000。你拿暴力解法去提交大概率能跑出正确结果但在超时的边缘反复横跳。更糟糕的是暴力解法的去重也很麻烦无序数组里找到[-1, 0, 1]和[0, 1, -1]本质上是同一个三元组你得先把每个三元组内部排序再塞进一个 Set 才能去重空间上又亏了一层。2.2 暴力解法也要会写它能帮你暴露问题我建议每个刚开始刷题的人都亲手写一遍暴力解法。不是为了提交而是为了理解一个关键转折——为什么“排序”会成为这道题的破局点。先看一段 Java 暴力版public ListListInteger threeSumBrute(int[] nums) { SetListInteger set new HashSet(); int n nums.length; for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (nums[i] nums[j] nums[k] 0) { ListInteger triple Arrays.asList(nums[i], nums[j], nums[k]); Collections.sort(triple); set.add(triple); } } } } return new ArrayList(set); }这段代码的问题除了 O(n^3) 时间还有一处隐蔽的逻辑Collections.sort(triple)在每一次命中三元组时都对三个元素排序。你可以说“反正只有三个数”但这段代码背后的去重思路是“先排序再塞Set”它其实是在暗示你排序能统一三元组的形态。如果你让整个数组从一开始就是有序的这个排序动作就完全不需要了去重也会变得极其简单。这就是优化的楔子。3. 排序 双指针把无序枚举变成有序逼近3.1 为什么先排序是本题最划算的一步很多人不理解排序本身要付出 O(n log n) 的时间成本怎么反而是加速的开始关键在于排序把“无序三元组”的问题变成了“有序序列上三个位置的组合问题”。排序前元素之间的先后关系没有意义你只能用下标嵌套排序后你可以利用“单调性”做决策甚至可以根据当前位置的数值提前判断“这条路走不通”。举个生活化的例子三个人比身高。无序的时候你想找身高和为某个值的组合只能一个个试如果三个人站成一排个头从左到右递增你看到左边最矮的人已经太高了就知道后面的人都不用看了。排序带来的就是这个“再一次确定两个方向都能推理由”的能力。这道题里排序让每个三元组天然满足nums[i] nums[left] nums[right]。这个顺序关系一出i是三元组的最小值left是中间值right是最大值。后续我们去重、剪枝全部建立在“有序”这个前提之上。3.2 把三数之和降维成两数之和固定i之后问题瞬间变成在i右侧的有序区间内寻找两个数left和right使得nums[left] nums[right] -nums[i]。这就是经典的“两数之和 II —— 输入有序数组”解法双指针一个在左端一个在右端根据加和与目标值的大小关系调整其中一个指针。让两数之和太大就把右指针往左挪太小就把左指针往右挪。每一轮比较指针要么左移要么右移不会走回头路所以一趟扫描是线性的 O(n)。最外层固定i要 O(n)于是整体复杂度从 O(n^3) 降到 O(n^2)。这个降维思路在后续“四数之和”里还会再套用一次本质上就是“固定一层循环剩下的问题降维”。3.3 双指针为什么一定能覆盖所有组合这是很多人心里没底的地方你跳着移动指针怎么确定不会漏掉组合关键点在于“有序”保证了一个决定性的事实当left指向当前能指向的最小未访问元素、right指向当前能指向的最大未访问元素时任何一次指针移动都是根据当前加和与目标值的大小关系做出的“确定性排除”。当前sum 0说明三元组太小。此时如果右指针再往左走只会让 sum 更小绝对不可能凑齐目标所以唯一可行的方向是增大左指针。当前sum 0同理只能缩小右指针。这种“每一步都排除一整片区域”的方式和二分搜索是同一个思想——利用有序性拿掉不可能的区域。所以双指针扫描不会漏不是玄学是数学上的必然。4. 双指针扫描的完整实现代码与逐行解读4.1 标准解法Java 版先给出一版可以直接 AC 的 Java 实现public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); if (nums null || nums.length 3) { return res; } Arrays.sort(nums); int n nums.length; for (int i 0; i n - 2; i) { // 剪枝排序后 nums[i] 是当前可用的最小元素 if (nums[i] 0) { break; } // 外层去重跳过重复的 i 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; }如果你更常用 Python逻辑完全一致def threeSum(nums): nums.sort() n len(nums) res [] 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 res4.2 逐块解读主循环的意图外层为什么只走到n - 2因为i至少要给left和right留出两个位置。写成i n - 2比i n更清晰也避免最后一轮无意义的扫描。内层while (left right)是真正的扫描区间。当sum 0时我们把当前三元组放入结果然后立即移动两个指针。很多初学者会在这里问“为什么找到一组后还要继续移动指针而不是 break”因为固定nums[i]之后有序区间里可能还存在其他合法的(left, right)组合。比如[-2, 0, 0, 2, 2]中固定i 0就能找到[-2, 0, 2]这组解而且左指针从 1 到 2、右指针从 4 到 3 还能再找到一组。所以找到一组后必须“压缩窗口”继续向内搜索。复杂度方面排序 O(n log n)外层 O(n)内层双指针 O(n)整体 O(n^2)。额外空间主要是结果数组如果不算结果存储只用了常数级额外空间。5. 去重是本题真正的分水岭三个位置三种写法5.1 外层i的去重为什么是nums[i] nums[i - 1]这是这道题被问烂了、也写错最多的一个点。正确写法是if (i 0 nums[i] nums[i - 1]) { continue; }但很多人会不自觉地写成if (i 0 nums[i] nums[i 1]) { continue; }两种写法看着只差一个符号结果天差地别。nums[i] nums[i1]的意思是如果当前元素和下一个元素相同就把当前元素跳过。但问题是在i之外还有一层left指针它恰好可以从i 1开始取到那个被比较的元素。举个例子数组排序后为[-1, -1, 0, 1, 2]。当i 0时nums[0] -1。如果写成nums[i] nums[i1]发现nums[0] -1 nums[1]直接 continue跳过了i 0。但此时left 1和right 4的组合是nums[1] -1, nums[4] 2和i 0的-1加在一起正好是[-1, -1, 2]这一组合法解。因为这组解的全部三个元素恰好都包含在数组里且其最小的-1来自两个不同位置。你用“当前元素等于下一个元素”来跳过就把解丢掉了。正确写法nums[i] nums[i-1]的意思是当前这个元素在之前的i位置已经作为“最小值”处理过了再处理一次必然产生重复三元组。注意“最小值”这个前提——i在每个三元组中扮演的永远是三个位置中最靠左的一个。同一个数值出现在更靠左的位置时已经枚举过所有组合出现在i这个位置时如果值相同就是纯重复。这个区别怎么记我的土办法是i的去重是“向后看还是向前看”的选择题。向前看和上一个比较保证每个相同值只以最小下标出现一次向后看和下一个比较会把“第一个位置还没用完”的合法场景误杀掉。和前面出现过的大哥比准没错。5.2 找到一组解后的left/right去重拿到sum 0的结果后立即做两个小循环while (left right nums[left] nums[left 1]) { left; } while (left right nums[right] nums[right - 1]) { right--; }这个去重和i的去重有一个微妙的错位left跳过的是“和下一个相同”right跳过的是“和上一个相同”。原因是方向不同。left从左往右移动如果当前值和下一个值相同说明下一个位置取到的元素和当前元素完全一致会导致重复三元组所以直接把它消耗掉right从右往左移动判断逻辑镜像对称。举个例子数组为[0, 0, 0, 0]。固定i 0nums[0] 0。left 1right 3sum 0结果加入[0, 0, 0]。此时 if 去重nums[1] nums[2]left跳到 2nums[3] nums[2]right跳到 2。循环结束。如果不做这两步去重下一次left 2, right 2时循环已经结束但left和right在sum 0分支后仍会各走一步下一轮就会重复计算[0, 0, 0]。5.3 三大去重位置总结位置判断条件核心作用外层ii 0 nums[i] nums[i-1]防止同一最小值重复枚举内层leftleft right nums[left] nums[left1]防止同一中间值重复入结果内层rightleft right nums[right] nums[right-1]防止同一最大值重复入结果记住了这张表就能回答面试中“你不用 Set 怎么保证不重复”的追问不是靠哈希而是靠有序数组上的“相等值只取最靠边的一个位置”原则。三个去重位置分别约束三元组里的三个位置缺一不可。6. 边界条件与增量剪枝宁可多写判断不要模糊过关6.1 输入边界空数组、长度不足、全相同元素最常见的防呆处理if (nums null || nums.length 3) { return res; }这个判断必须放在排序之前。length 3时不可能存在三元组直接返回空列表null检查是为了防止 NPE。这两个判断虽然简单但很多人在紧张时会漏一漏就是运行时错误。还有一类边界是“全相同元素”比如[1, 1, 1, 1]。排序后外层i 0时nums[0] 0直接 break返回空结果。[0, 0, 0]则会正常进入sum 0分支加入一组[0, 0, 0]后由于内层去重会跳过所有重复的 0循环正常结束。6.2 剪枝 1最小元素大于 0直接结束if (nums[i] 0) { break; }排序后nums[i]是三元组中的最小元素。如果它已经大于 0那么任何包含它的三元组都严格大于 0不可能和为 0。这是最强力的剪枝在负数较少的集合里能大幅减少扫描次数。这里用break而不是continue因为数组是有序递增的当前i已经太大后面的i只会更大直接全部退出。6.3 剪枝 2当前最小组合仍然过大直接退出if (nums[i] nums[i 1] nums[i 2] 0) { break; }nums[i]与它右侧最小的两个数相加已经是“以nums[i]为最小值的三元组”里的最小可能和。如果它都大于 0说明任何以nums[i]开头的三元组都不可能与 0 相等后面的i只会让和更大直接 break。这也是合法剪枝因为它不会排除任何可能的解只提前终止不可能的分支。6.4 剪枝 3当前最大组合仍然小于 0右移iif (nums[i] nums[n - 1] nums[n - 2] 0) { continue; }nums[i]与数组右侧最大的两个数相加的和是以nums[i]为最小值的三元组里最大的可能和。它仍然小于 0说明nums[i]太小了无论双指针怎么配都凑不出 0。这时continue到下一个i即可。注意这里用continue而非break因为增大i后最小元素变大仍然可能存在合法组合不能结束循环。这三条剪枝在代码里的顺序很有讲究。nums[i] 0是“一刀切”后面两条是基于当前i位置的“局部提前退出”或“局部跳跃”。它们不是必须写的但面试或者比赛时写上既是加分项又能显著加快执行。我自己的习惯是至少保留第一条后两条根据现场状态决定要不要补。6.5 大整数相加溢出用 long 还是用逻辑规避这是一个容易被忽略的边界。在 Java 和 C 中int相加可能溢出。比如nums[i] 1000000000另外两个数也是接近这个量级三数之和直接爆掉 int 范围结果变成一个负数判断逻辑全乱。简单做法是把sum声明为longlong sum (long) nums[i] nums[left] nums[right];在参加 LeetCode 周赛或者打算法竞赛时我更倾向于用long一劳永逸。但如果是写规范工程代码可以在判断nums[i]时就规避掉极端值带来的风险多加一两条提前剪枝即可。7. 用测试用例复盘一次从超时到 AC 的完整调试7.1 覆盖全场景的测试用例组不管你是自己刷题还是给别人讲题手边最好备一套覆盖各种边界的测试用例测试输入期望输出验证要点[-1, 0, 1, 2, -1, -4][[-1, -1, 2], [-1, 0, 1]]标准场景包含跨元素组合[0, 0, 0][[0, 0, 0]]全零至少一组解[0, 1, 1][]无法凑零[0, 0][]长度不足[-1, -1, 2][[-1, -1, 2]]两重相同最小元素必须保留一组[-1, -1, -1, 2][[-1, -1, 2]]三个相同的 -1 只能产生一组解[1, 1, 1, 1][]最小值大于 0 直接剪枝[0, 0, 0, 0][[0, 0, 0]]多个相同值只保留一组我调试时最常用来验去重的就是[-1, -1, -1, 2]。如果i层去重写错成nums[i] nums[i1]这个用例会直接挂出空结果因为你把唯一一个可以组成[-1, -1, 2]的“第一个 -1”跳掉了。7.2 指针移动的完整推演我用[-1, 0, 1, 2, -1, -4]手动走一遍双指针你在纸上跟着画一遍会对代码有完全不同的理解。排序后数组变为[-4, -1, -1, 0, 1, 2]。i 0nums[0] -4。目标变成left right 4。初始left 1, right 5-1 2 1小于 4所以left到 2——等等这里要小心nums[2]也是-1合理因为-1 2 1 4必须增大左指针。left 2后仍太小继续left 30 2 2 4left 41 2 3 4。left已经到 4而right 5left right成立但3仍然小于 4left到 5循环结束。没有匹配。i 1nums[1] -1。注意nums[1] nums[0]不nums[1] -1nums[0] -4不重复所以继续。目标变成left right 1。初始left 2, right 5-1 2 1命中得到[-1, -1, 2]。然后内层去重nums[2] nums[3]吗nums[3] 0不相等左指针跳到 3nums[5] nums[4]吗2和1不等右指针跳到 4。left 3, right 4继续0 1 1命中得到[-1, 0, 1]。再去重nums[3] nums[4]吗0和1不等nums[4] nums[3]吗不等。left到 4right--到 3循环结束。i 2nums[2] -1但nums[2] nums[1]外层去重生效跳过。i 3nums[3] 0不重复。目标变成left right 0。初始left 4, right 51 2 3 0right--right 4left right不成立结束。最终输出[[-1, -1, 2], [-1, 0, 1]]。手动推两遍之后你会注意到一个事实双指针扫描真正命中的情况远少于循环遍历的次数。大部分时候都在根据和的正负调整指针一步排除一片区域。这就是它高效的原因。7.3 调试技巧打印中间状态如果代码仍然出错最快的排查方式是临时打印每次进入内层循环时的i、left、right、sum以及每次加入结果的元素System.out.println(i i left left right right sum sum nums[i] nums[i]);观察输出你能立刻看出是外层i跳多了还是内层去重把相邻位置一并跳掉了或者指针移动方向反了。我自己刷题时一旦出现“输出结果比预期少一组”的情况基本都指向i层去重写错一旦出现“死循环或结果重复”基本都指向sum 0分支后忘记移动指针——那会导致同一组解被反复加入或left、right原地卡死。7.4 高频错误对照表错误表现常见根因修复方式结果缺失特别是含两个相同元素的组合i层去重误用nums[i] nums[i1]改成nums[i] nums[i-1]结果重复找到一组后未做内层去重补两个 while 跳过逻辑死循环sum 0分支后left/right--没写手动移动指针超时没有外层剪枝或没用双指针先确认是否 O(n^2)再加剪枝空指针/数组越界没检查 null 和长度排序前加length 3判断大整数溢出直接用 int 累加用 long 或提前剪枝8. 刷完这题下一步怎么扩展三数之和做完有几个直接相关的变体题值得顺手刷掉因为它们的套路完全一脉相承。最接近的三数之和LeetCode 16同样是排序加双指针差别在于不是找等于 0 的组合而是维护一个最小差值。难度增加不大但能训练你“目标值动态变化”的处理能力。四数之和LeetCode 18本质是三数之和套一层循环——固定两个数剩下两个用双指针扫描。去重的思路和三数之和完全一致只要你能把三数之和的去重逻辑想透四数之和只是“平移一层”的问题。三数之和小于 target 的计数LeetCode 259这题我不确定现在是否还在付费题库里但如果是非常值得练。它要求你统计满足a b c target的三元组个数不要求输出具体组合。定点i后只要nums[i] nums[left] nums[right] target那么left到right之间的所有位置作为right的取值时都满足条件直接累加right - left即可。这题是“双指针区间可一次性累加多个解”的典型能进一步强化你对方针移动数学含义的理解。我个人刷题的建议是这三题连续做中间隔不超过两天。你会发现自己在做第三题时已经能熟练地写出排序、去重、移动指针三段结构甚至不需要再看模板。这才是真的掌握而不是背答案——背答案只能撑到下次面试理解算法却能让你在遇到变形题时举一反三。三数之和这道题的价值说大不大说小不小。它就是那种“开学以为会合上书就废”的代表。花时间把每一步的原理想清楚比多刷十道简单题更有用。下次再有人说“三数之和不就是排序加双指针吗”你可以笑着把去重的三个位置、剪枝的三个条件、边界的五个用例全部甩给他——那才叫真会。