企业官网建设流程全解析

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 List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Set<List<Integer>> 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 是去不掉重的 List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]); list.sort(null); set.add(list); } } } } return new ArrayList<>(set); }

这个版本的复杂度是 O(n³)，n 稍微大一点（比如 3000），就要执行 270 亿次循环，根本跑不完。而且去重逻辑在暴力解法里特别别扭：List<Integer>的直接equals比较的是内容，但如果三个数的顺序不同，[-1,0,1]和[0,1,-1]会被当成两个不同结果，所以你还得先排序再放进 Set。

更好的思路是换赛道：与其三重循环碰运气，不如先把数组排序，让“找两数之和”这个子问题变成可以用双指针线性解决的形态。这就是双指针解法的核心思路。

2. 双指针解法的核心心法

2.1 一句话概括整体思路

排序 + 固定一个数 + 双指针收缩。

具体来说：先把数组从小到大排序，然后外层循环固定第一个数nums[i]，问题就转化成：在i后面的区间[i+1, 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 List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> 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[i+1] + nums[i+2] > 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，因为要保证i+1和n-2是两个不同的位置，否则会拿同一个数算两次，逻辑就错了。

4. 常见错误与排查实录

4.1 外层去重写错方向导致漏解

这是最常见的错误。我把代码写成了nums[i] == nums[i+1]去重，结果在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返回。但List<Integer>的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 常见问题速查表

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 List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> 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-3，left必须小于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]，然后外层i=0固定-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]，i=0固定 0，target=0，left指向第一个 1，right指向第二个 1，sum=2，大于 0，right--，循环结束。没有任何解，输出空列表，这是对的。

如果我在内层去重时把条件写反了，这个用例就会输出错误的[0,1,1]。手推一遍能省下很多调试时间。

6.3 实测运行时间对比

我在本地用 3000 长度的随机数组测过三个版本的耗时：

暴力解法根本没法用，双指针加剪枝后性能提升接近百倍。这组数据我经常在技术分享时用来强调算法优化的实际价值。

7. 写在最后的一点经验

三数之和这道题，我前前后后刷了不下十遍，每次重刷都有新收获。一开始是背模板，后来理解了双指针为什么能这样移动，再后来能从这道题延伸到四数之和、最接近的三数之和，形成了一整套双指针解题体系。

我个人在实际操作中最深刻的体会是：算法题的提升不在刷题数量，而在每道经典题背后那套可迁移的思维框架。你能不能用一句话讲清楚这道题的思路，能不能把双指针移动的数学依据推导出来，能不能独立调试出去重 bug，这些才是真正让你在面试中脱颖而出的能力。

最后再分享一个小技巧：做双指针类题目时，先别急着写代码，在纸上画出数组排序后的样子，用两个手指代表左右指针，模拟几轮移动。这个看起来笨的方法，比任何 debugger 都管用，因为它强迫你理解每一步移动背后的逻辑，而不是凭感觉写代码。希望这篇三数之和的解析能帮你真正吃透双指针，后面遇到任何双指针变形题，你都能一眼看穿本质。