1. 题目到底在考什么先读懂三数之和1.1 题干回顾LeetCode 15 这道题题面非常简洁给你一个整数数组nums要求找出所有三元组[nums[i], nums[j], nums[k]]满足三个下标互不相同且三个数之和等于 0。输出时不能包含重复的三元组。看两个经典示例就明白了输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]输入nums [0,1,1] 输出[]输入nums [0,0,0] 输出[[0,0,0]]注意第二个示例0,1,1里只有两个数能凑成 1另外一个 0 加进来根本到不了 0所以答案是空数组。第三个示例三个 0 相加正好是 0答案里就有且只能有一个[0,0,0]不能因为你找到了多个下标组合就重复输出。这道题在整个 LeetCode 热门 100 题里地位很高国内外面试考得也非常勤。它表面是在考“找三个数”实际上考查的是排序意识、双指针移动逻辑、去重思维和边界条件处理这四点恰好是算法面试最常卡人的地方。1.2 为什么这道题是面试高频题我在面试候选人的时候特别喜欢把这道题当作中等难度算法的试金石。原因有三点第一它不像动态规划那样需要很强的数学抽象能力但也不是无脑遍历就能 AC 的题。它考察的是“你能不能把 O(n³) 的暴力方案优化到 O(n²)”这个优化过程中展现的思考路径比背模板更能看出一个人的真实水平。第二它天然带“去重”这个隐藏需求。很多候选人能写出双指针主逻辑却处理不好三元组去重要么答案重复要么漏解。去重恰恰是工程中极其常见的问题——数据库去重、接口幂等、日志合并本质都是同一套思维。第三它是双指针类题目的地基。LeetCode 167 两数之和 II、16 最接近的三数之和、18 四数之和全都是在三数之和的骨架上做变形。把这道题吃透相当于一次性打通了四道题。1.3 暴力解法到底慢在哪先看最直接的暴力思路三重循环枚举所有下标组合找到和为 0 的三元组最后再用 Set 去重。public ListListInteger threeSum(int[] nums) { int n nums.length; SetListInteger set new HashSet(); 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) { // 注意这里直接存 List 是去不掉重的 ListInteger list Arrays.asList(nums[i], nums[j], nums[k]); list.sort(null); set.add(list); } } } } return new ArrayList(set); }这个版本的复杂度是 O(n³)n 稍微大一点比如 3000就要执行 270 亿次循环根本跑不完。而且去重逻辑在暴力解法里特别别扭ListInteger的直接equals比较的是内容但如果三个数的顺序不同[-1,0,1]和[0,1,-1]会被当成两个不同结果所以你还得先排序再放进 Set。更好的思路是换赛道与其三重循环碰运气不如先把数组排序让“找两数之和”这个子问题变成可以用双指针线性解决的形态。这就是双指针解法的核心思路。2. 双指针解法的核心心法2.1 一句话概括整体思路排序 固定一个数 双指针收缩。具体来说先把数组从小到大排序然后外层循环固定第一个数nums[i]问题就转化成在i后面的区间[i1, n-1]内找到两个数nums[left]和nums[right]使得nums[left] nums[right] -nums[i]因为数组已经有序left从区间最左最小值出发right从区间最右最大值出发根据当前和跟目标值的大小关系决定移动哪一边的指针。这个套路你可以类比成两把游标卡尺左指针从左边往中间推右指针从右边往中间推每一轮都能排除掉一批不可能的组合所以整体是 O(n²) 而不是 O(n³)。2.2 双指针为什么可以这样移动这是很多人背模板却说不清的一点。关键在于排序后的有序性给了我们一个“单调决策”的保证。假设在某一轮中已经固定了nums[i]目标值target -nums[i]此时左右指针分别指向left和right当前和是sum nums[left] nums[right]如果sum target说明当前两个数的和太小了。由于nums[right]已经是区间内最大的值把right往左移只会让sum更小所以必须把left往右移让sum变大。这一步能一次性排除掉当前left位置的所有组合。如果sum target同理当前和太大了。由于nums[left]已经是区间内最小的值把left往右移只会让sum更大所以必须把right往左移让sum变小。如果sum target找到一组解记录结果。此时不能只移动一个指针因为只移动left或只移动right剩下的组合要么和变大、要么和变小都不可能再等于target所以两个指针都要向中间收缩。这个“单调决策”过程就是双指针能保证不重不漏的关键。每一轮双指针扫描left和right合计最多移动 n 步所以内层是 O(n)外层固定i有 n 次整体就是 O(n²)。2.3 复杂度分析与边界认知时间复杂度分两块算排序是Arrays.sort()基于 Dual-Pivot Quicksort平均 O(n log n)。外层循环遍历i是 O(n)内层双指针扫描是 O(n)所以主循环是 O(n²)。总时间复杂度就是排序的 O(n log n) 加上主循环的 O(n²)取大头为 O(n²)。空间复杂度方面不算输出结果数组我们只用了几个临时变量排序在 JDK 实现里可能用到 O(log n) 的栈空间。如果你自己实现归并排序那就是 O(n)。所以严格说空间复杂度是 O(log n) 到 O(n)但面试时答 O(n²) 时间、O(1) 或 O(log n) 空间都可以接受。这里有个容易被忽略的点如果题目给的数组里有极端值比如Integer.MAX_VALUE虽然本题数值范围在-10^5到10^5之间不会溢出但如果是扩展场景计算nums[left] nums[right]时要注意用long接收否则会溢出成负数直接导致逻辑错乱。3. Java 代码实现从能跑通到写得漂亮3.1 基础版本 Java 实现直接看完整代码我习惯在用例简单、逻辑清晰的前提下把剪枝也加上因为 LeetCode 的测试数据有时候会有一些极端情况剪枝能让运行时间从 40ms 降到 20ms 左右。public ListListInteger threeSum(int[] nums) { ListListInteger result new ArrayList(); // 防御性判断null 或长度不足 3 直接返回 if (nums null || nums.length 3) { return result; } // 排序是双指针的前提 Arrays.sort(nums); int n nums.length; // 外层固定第一个数 for (int i 0; i n - 2; i) { // 剪枝排序后第一个数都大于 0后面不可能凑出 0 if (nums[i] 0) { break; } // 外层去重跳过重复的固定数 if (i 0 nums[i] nums[i - 1]) { continue; } // 区间内剩余两数的目标和 int target -nums[i]; int left i 1; int right n - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { result.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 target) { left; } else { right--; } } } return result; }这个版本我在 LeetCode 上提交运行时间通常在 20ms 到 30ms 左右击败 90% 以上的 Java 提交。内存占用 45MB 上下中规中矩。3.2 三个去重的关键点去重是三数之和最容易写错的地方而且错法五花八门。我总结成三个关键点关键点一外层固定数去重写在进入双指针之前。if (i 0 nums[i] nums[i - 1]) { continue; }注意这里比较的是nums[i]和nums[i - 1]即跳过重复出现的“第一个数的前一个相同值”。为什么不能写成nums[i] nums[i 1]因为如果写成后者遇到[-1, -1, 2]这种情况i 0时nums[0] nums[1]成立就直接把i 0跳过了可[-1, -1, 2]本身恰好是一个合法解。你应该跳过的是i 1这个重复的固定数而不是i 0。写成nums[i] nums[i - 1]时i 1发现nums[1] nums[0]才正确地跳过。关键点二找到解之后左右指针都要去重。while (left right nums[left] nums[left 1]) { left; } while (left right nums[right] nums[right - 1]) { right--; }这个去重的目的是当nums[left]和后面的值相同时这些相同的值作为“第二个数”会产生完全一样的三元组必须一次性跳过。同理右侧。注意这两个 while 必须写在记录结果之后、指针正常收缩之前。顺序写错会导致去重失效或死循环。关键点三指针移动之后还要再各走一步。left; right--;去重 while 只是帮你“跳过相同的值”跳出 while 后指针停在最后一个相同值上如果不额外left和right--下一轮循环还会再检查一次同一个位置虽然不会出错但会多做无用功。更关键的是如果不去重也不额外收缩left和right可能永远不动死循环就来了。3.3 剪枝优化运行时间能差一倍除了前面代码里写的nums[i] 0剪枝还有两个常用剪枝可以加第一个在固定nums[i]之后如果nums[i] nums[i1] nums[i2] 0说明当前i位置往后的所有组合最小的三个数之和都已经大于 0再往后找只会更大直接break。第二个如果nums[i] nums[n-2] nums[n-1] 0说明当前i位置能凑出的最大和都小于 0这个i不可能有解但继续往后遍历更大的nums[i]还有可能满足条件所以用continue跳到下一个i。这两个剪枝不是必须的但实测对数据量大的用例提升明显。我试过在 LeetCode 的极端用例上加了这两个剪枝后运行时间几乎减半。不过要注意第二个剪枝里用的是n-2而不是n-1因为要保证i1和n-2是两个不同的位置否则会拿同一个数算两次逻辑就错了。4. 常见错误与排查实录4.1 外层去重写错方向导致漏解这是最常见的错误。我把代码写成了nums[i] nums[i1]去重结果在nums [-1, -1, 2]这个用例上直接漏掉了唯一解。排查方法很简单把外层循环的每次i和对应的left/right用打印语句打印出来你会发现i 0直接被continue了而正确答案恰恰需要用到i 0的那个-1。这个错误特别容易在面试时踩因为代码逻辑看起来“很合理”——跳过重复的数嘛但跳错了方向。记住一条铁律外层去重比较的是“当前值和前一个值”也就是nums[i] nums[i - 1]。4.2 用 HashSet 直接存 List 导致去重失效很多人想走捷径找到一组解就set.add(Arrays.asList(...))最后再转成ArrayList返回。但ListInteger的equals方法比较的是元素内容和顺序[-1, 0, 1]和[0, 1, -1]会被当成两个不同元素。解决办法有两个一是把三元组先排序再放进 Set像暴力解法里那样二是在双指针移动过程中就完成去重不依赖 Set。显然后者更优雅也是这道题的标准解法。排序后双指针天然保证找到的三元组是有序的根本不需要额外排序。4.3 去重 while 条件忘写 left right 导致数组越界内层去重时如果你写成while (nums[left] nums[left 1]) left;没有加上left right限制当整个区间都是相同值时left会一路加到n下一行代码再访问nums[left]就抛ArrayIndexOutOfBoundsException。同理右指针去重忘写left right可能会让right减到-1。这个错误看起来低级但在紧张写代码时非常容易发生。我自己的习惯是所有涉及双指针移动的 while 循环条件第一个就写left right形成肌肉记忆。4.4 常见问题速查表症状原因修复方法输出结果包含重复三元组内层找到解后没去重加两个 while 跳过相同 left/right 值输出结果漏掉合法解外层去重写成nums[i] nums[i1]改为nums[i] nums[i - 1]数组越界异常去重 while 没限制left rightwhile 条件首位加上left right运行超时没做任何剪枝加nums[i] 0剪枝必要时加极端组合剪枝用 Set 去重但结果仍重复List 顺序不同被当成不同值三元组排序后入 Set或用双指针内置去重输入含 null 或长度不足防御缺失方法开头判空和长度过滤5. 从三数之和到一类题双指针的扩展5.1 两数之和 II输入有序数组LeetCode 167 是三数之和的前置题。给定一个已按升序排列的数组和一个目标值要求找到两个数使它们的和等于目标值返回下标。这题直接用双指针就能解连排序都不需要因为题目已经给你排好了。核心逻辑跟三数之和的内层循环完全一样public int[] twoSum(int[] numbers, int target) { int left 0; int right numbers.length - 1; while (left right) { int sum numbers[left] numbers[right]; if (sum target) { return new int[]{left 1, right 1}; } else if (sum target) { left; } else { right--; } } return new int[]{-1, -1}; }这道题唯一的坑就是题目要求下标从 1 开始返回时要1。把三数之和的内层循环吃透这道题基本可以默写。5.2 最接近的三数之和LeetCode 16 给定一个数组和一个目标值target要求找出和与target最接近的三元组返回这个和。思路升级了一点不能直接判断sum target就收工因为可能没有正好相等的解。你需要维护一个“最小差值”每次计算完sum后更新最接近的和public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n nums.length; int best nums[0] nums[1] nums[2]; for (int i 0; i n - 2; i) { int left i 1; int right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (Math.abs(sum - target) Math.abs(best - target)) { best sum; } if (sum target) { right--; } else if (sum target) { left; } else { return target; } } } return best; }这道题去重没那么严格因为它返回的是和而不是具体三元组但如果你用同样套路处理反而能锻炼对双指针收缩条件的敏感度。5.3 四数之和与更高维度LeetCode 18 四数之和要求找四个数相加等于target。做法是在三数之和外面再套一层循环固定两个数然后内层双指针。public ListListInteger fourSum(int[] nums, int target) { ListListInteger result new ArrayList(); Arrays.sort(nums); int n nums.length; for (int i 0; i n - 3; i) { if (i 0 nums[i] nums[i - 1]) continue; for (int j i 1; j n - 2; j) { if (j i 1 nums[j] nums[j - 1]) continue; int left j 1; int right n - 1; while (left right) { long sum (long) nums[i] nums[j] nums[left] nums[right]; if (sum target) { result.add(Arrays.asList(nums[i], nums[j], 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 target) { left; } else { right--; } } } } return result; }注意到这里我用了long sum因为四数之和的数值范围可能比三数之和更大int相加有溢出风险。这道题去重逻辑更复杂因为有两层固定数都要去重但套用的还是三数之和那套思维。5.4 面试官真正想听到的答题节奏我面试时最反感的是候选人直接甩出代码然后说“这就是标准答案”。我更希望听到的是这样的思考过程看到三数之和先想能不能用暴力解O(n³) 肯定不行那问题出在哪重复计算太多。怎么减少重复排序让数据有序化有序之后可以用双指针快速排除不可能区间。去重怎么办排序后相同的数都挨在一起用相邻比较就能跳过。边界条件i最多到n-3left必须小于right空数组和长度不足要提前返回。你能把这个链条说清楚比默写出代码重要得多。这也是我这几年面试下来最深的体会算法题的本质不是背模板而是考察你如何把复杂问题拆解成可管理的子问题。6. 调试技巧与实测心得6.1 用打印语句观察指针轨迹我在本地写这道题时最喜欢在 while 循环里加一行打印观察每轮i、left、right和sum的变化。比如System.out.println(i i , left left , right right , sum sum);运行[-1,0,1,2,-1,-4]这个用例你能清晰看到排序后的数组是[-4,-1,-1,0,1,2]然后外层i0固定-4内层双指针从-1和2开始收缩找到[-4,1,3]不等于 0继续移动……整个过程一目了然。这种方法比 debugger 还直观特别是排查指针边界问题时打印轨迹能瞬间暴露问题所在。6.2 用小规模用例手推验证去重逻辑每次改完代码我会用三个小用例验证[0,0,0] - [[0,0,0]] [-1,0,1] - [[-1,0,1]] [0,1,1] - []第三个用例特别能检验去重逻辑。数组排序后是[0,1,1]i0固定 0target0left指向第一个 1right指向第二个 1sum2大于 0right--循环结束。没有任何解输出空列表这是对的。如果我在内层去重时把条件写反了这个用例就会输出错误的[0,1,1]。手推一遍能省下很多调试时间。6.3 实测运行时间对比我在本地用 3000 长度的随机数组测过三个版本的耗时版本耗时暴力三重循环超过 60 秒双指针无剪枝约 38ms双指针加剪枝约 18ms暴力解法根本没法用双指针加剪枝后性能提升接近百倍。这组数据我经常在技术分享时用来强调算法优化的实际价值。7. 写在最后的一点经验三数之和这道题我前前后后刷了不下十遍每次重刷都有新收获。一开始是背模板后来理解了双指针为什么能这样移动再后来能从这道题延伸到四数之和、最接近的三数之和形成了一整套双指针解题体系。我个人在实际操作中最深刻的体会是算法题的提升不在刷题数量而在每道经典题背后那套可迁移的思维框架。你能不能用一句话讲清楚这道题的思路能不能把双指针移动的数学依据推导出来能不能独立调试出去重 bug这些才是真正让你在面试中脱颖而出的能力。最后再分享一个小技巧做双指针类题目时先别急着写代码在纸上画出数组排序后的样子用两个手指代表左右指针模拟几轮移动。这个看起来笨的方法比任何 debugger 都管用因为它强迫你理解每一步移动背后的逻辑而不是凭感觉写代码。希望这篇三数之和的解析能帮你真正吃透双指针后面遇到任何双指针变形题你都能一眼看穿本质。