最近刷LeetCode被第15题“三数之和”整得有点破防。倒不是说完全没思路而是“去重”这两个字看着简单写起来各种边界情况能把人绕晕。我估计不少朋友跟我一样明明双指针的思路门儿清一提交就是“输出重复三元组”或者“漏解”然后开始疯狂打补丁。这篇就把这道题从头到尾拆开揉碎重点说说去重到底在去什么、为什么这么去以及我踩过的那些坑希望能帮各位一次把这道经典题吃透。这道题是面试高频题也是LeetCode热门100题里的常客刷题指南里基本绕不开它。它考的不是什么高深算法而是你对“双指针”这个基础技巧的掌握程度以及对边界条件和逻辑细节的把控能力。说白了就是看你写代码的时候脑子清不清楚。适合所有正在准备算法面试、刷LeetCode的初学者和进阶者尤其是被各种“看似简单、实则细节拉满”的题目折磨过的朋友。1. 题目拆解从暴力解到双指针的思路跃迁1.1 先读懂题目在问什么题目要求很直白给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0。请你找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。这里“不重复”指的是三元组之间的不重复而不是三元组内部元素的顺序问题。比如[-1, 0, 1]和[0, 1, -1]在题目眼里就是同一个三元组只能保留一个。我第一次做的时候下意识就想暴力三重循环时间复杂度 O(n^3)n 如果到 3000 直接超时。就算勉强能跑去重也是个噩梦因为你需要对三个数都做去重判断稍不留神就漏掉或者重复。1.2 为什么是“排序 双指针”这是这道题的核心思想也是绝大部分题解的标准做法。排序是为了让数组有序这样才能利用双指针的单调性来优化搜索。具体思路是这样先对数组排序然后固定一个数 nums[i]再用两个指针 left 和 right 分别指向 i1 和 n-1。计算三数之和 sum nums[i] nums[left] nums[right]。如果 sum 0说明右侧的数太大了right 左移如果 sum 0说明左侧的数太小了left 右移如果 sum 0就记录下这个三元组。这个过程相当于把“找两个数等于目标值”的双指针问题套上了一层循环。时间复杂度从 O(n^3) 降到了 O(n^2)空间复杂度 O(1)不考虑排序的递归栈。注意排序是前提如果数组无序双指针的移动逻辑就不成立了。这也是这道题为什么先要排序的根本原因。2. 核心细节去重逻辑到底在去什么2.1 外层循环的去重i 的去重这是很多人第一个卡住的地方。固定 nums[i] 的时候如果nums[i] nums[i-1]那就说明这个数作为第一个元素的情况已经处理过了直接跳过也就是if (i 0 nums[i] nums[i-1]) continue;。这里有个细节特别容易搞错为什么是跟nums[i-1]比较而不是跟nums[i1]比较如果你写的是if (nums[i] nums[i1]) continue;那就会出大问题。比如数组是[-1, -1, 0, 1]正确的答案应该是[-1, 0, 1]这一个三元组。但如果用nums[i1]去重当 i0 时nums[0] nums[1] -1直接 continue 了就把这个正确答案给跳过了。而用nums[i-1]去重当 i0 时没有前一个元素不会跳过当 i1 时nums[1] nums[0]说明以 -1 开头的三元组已经找过了跳过完全没问题。这个逻辑说白了就是我们要保证每个不同的“第一个元素”只被处理一次。nums[i-1]能帮我们判断当前这个元素是不是第一次出现而nums[i1]会误判成“这个元素后面还有相同的所以跳过”但后面那个相同的元素根本还没被作为第一个元素处理过。2.2 内层双指针的去重left 和 right 的去重找到一组sum 0的解之后不能直接 break因为还可能存在其他组合。但在移动指针之前必须先做去重。比如数组是[-2, 0, 0, 2, 2]i 指向 -2left 指向第一个 0right 指向最后一个 2。sum 0记录[-2, 0, 2]。接下来如果 left 和 right 都只移动一位left 指向第二个 0right 指向第一个 2又得到一个[-2, 0, 2]这就重复了。所以标准的做法是记录完答案后先让 left 跳过所有和当前值相同的元素right 也跳过所有和当前值相同的元素然后再分别 left、right--进入下一轮判断。写成代码就是while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--;这里要注意判断条件里必须带left right不然 left 可能会越界。2.3 去重的时机什么时候去重什么时候不去重这个问题是我当初纠结最久的。为什么内层找到答案后要去重而没找到答案时sum 0 或 sum 0不需要去重其实你去不去重都不影响最终结果的正确性不去重只会多做几次无效的循环但去重确实能提升效率。关键在于你必须在找到答案后再去重否则可能漏解。举个例子数组是[-4, -1, -1, 0, 1, 2]i 指向 -4 时left 指向 -1right 指向 2sum -3 0leftleft 指向第二个 -1。如果此时我们做去重发现nums[left] nums[left-1]就跳过那么 left 就指向 0 了但实际上-4 -1 2 -3不等于 0所以这里跳过并不会漏掉正确答案。因为如果当前 left 的值组合不出答案它后面相同的值也组合不出答案除非第一个元素不同。但反过来如果在找答案前因为 left 和 left1 的值相同就跳过可能会跳过一种组合比如数组[-1, -1, 2]i 指向第一个 -1 时left 指向第二个 -1right 指向 2sum 0。如果你在找答案前看到 left 和 left1 相同就跳过那 left 移到第二个 -1 的位置反而错过了正确答案。所以最稳妥的逻辑就是先正常移动指针找答案找到答案后再去重然后继续找。3. 实操过程完整代码与参数选择3.1 我最终写出来的版本我把最终的代码贴出来这个版本我实测了好几个用例包括各种极端情况都能正常通过。这里用 Java 写其他语言思路完全一样。class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); int n nums.length; // 排序是前提 Arrays.sort(nums); for (int i 0; i n - 2; i) { // 最小的数都大于0后面的组合不可能等于0 if (nums[i] 0) break; // 外层去重i和i-1比较 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])); // 内层去重跳过重复的left和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; } }3.2 关键参数的考量我逐个说说每个判断条件的意义理解了这些才算真的会了。先看外层循环的边界i n - 2。因为我们要找三个数i 最多到倒数第三个位置否则 left 和 right 就没地方放了。if (nums[i] 0) break;这个优化很关键。数组是升序排列的如果 nums[i] 都大于 0 了那后面两个数肯定也大于 0三个正数加起来不可能等于 0。直接跳出整个循环省掉后面所有的无用功。if (i 0 nums[i] nums[i - 1]) continue;前面详细讲过为了保证当前元素是第一次作为第一个数出现。内层while (left right)是双指针的基本框架只要两个指针没相遇就继续找。最后看内层去重的写法为什么放在 sum 0 的分支里。因为只有在这一刻我们才确定了一个有效的三元组此时跳过重复的 left 和 right 是安全的不会漏解。而且注意我是先用 while 跳过重复值再统一 left、right--这样能保证指针最终一定指向新的不同值。3.3 一个我常用的调试小技巧当你实在搞不清楚某个边界情况时别干想直接把数组打印出来手动模拟指针的移动过程。我当初就是卡在i 0 nums[i] nums[i - 1]这段后来拿[-1, -1, 2]这个用例手动走了一遍才彻底明白为什么不能用nums[i1]。纸上得来终觉浅手动跑一遍胜过看十遍题解。4. 常见问题与排查技巧实录4.1 输出结果有重复三元组这是最常遇到的问题。如果你重复了先检查外层去重是不是写成了nums[i] nums[i 1]。如果是改回nums[i] nums[i - 1]基本就能解决。还有一种情况是内层去重压根没写。有些朋友找到 sum 0 之后就直接 left、right--没跳过中间相同的值这就导致同一轮循环里可能出现重复的三元组。解决办法就是加上我前面说的两个 while 循环。4.2 输出结果漏掉了某些三元组漏解的情况一般出在两个地方。一个是外层循环用了nums[i] nums[i1]去重把不该跳过的答案跳过了另一个是内层在 sum 不等于 0 的时候做了去重导致指针跳过了可能组成答案的位置。记住一个原则只有在 sum 0 时才做内层去重。sum 0 或 sum 0 时直接移动对应指针即可。4.3 超时问题双指针的时间复杂度已经是 O(n^2) 了一般不会超时。但如果你还是超时看看是不是没有加if (nums[i] 0) break;这个剪枝。某些极端情况下这个优化能省掉大量无用的循环。4.4 常见问题速查表症状可能原因解决办法结果重复外层去重用了 nums[i1]改为 nums[i-1]结果重复内层找到答案后未去重加两个 while 循环跳过重复值结果漏解外层错误跳过检查去重方向使用 nums[i-1]结果漏解内层 sum ! 0 时去重只在 sum 0 时去重超时缺少剪枝加 if (nums[i] 0) break数组越界内层 while 没写 left right加上边界判断5. 从三数之和到双指针的通用套路刷了这么多题我慢慢发现双指针这个套路是真的香。不说远的就说LeetCode上另外几个高频题5. 最长回文子串、494. 目标和、875. 爱吃香蕉的狒狒它们本质上都能看到双指针或者类似思想的影子。最长回文子串用中心扩展法其实也是双指针的变体一个往左走一个往右走找到最长回文边界。爱吃香蕉的狒狒虽然是个二分查找题但你在 check 函数里维护的“吃完一堆香蕉需要的时间”本质上也是在用某种指针或者累加的方式逼近答案。三数之和处理去重的方式完全可以迁移到 18题四数之和 上只是多一层循环多一次去重。你在三数之和里搞懂了 i 的去重逻辑四数之和里前两个数的去重就照着写基本不会出大问题。我个人的体会是算法这东西刷题不在多在于把一类套路吃透。三数之和这道题看似简单但它综合了排序、双指针、去重、边界判断、剪枝优化几乎把面试爱考的基础考点一网打尽了。你把这道题嚼碎了比囫囵吞枣刷十道简单题都管用。最后再分享一个小技巧如果你在面试中遇到这题先说暴力解再说优化到双指针把时间复杂度从 O(n^3) 讲到 O(n^2) 的过程展示出来这本身就是很好的沟通加分项。然后写代码的时候主动把去重逻辑讲清楚面试官会知道你是真的懂了而不是背题。做题嘛做一道就吃透一道后面类似的题就是送分题。