在算法进阶的道路上，“三数之和”是一道标志性的分水岭题目。掌握LeetCode三数之和双指针解法的核心价值，远不止于学会一种解题技巧。它深刻地诠释了如何通过排序预处理、固定锚点与相向双指针的协同，将时间复杂度从O(n³)的暴力枚举优化至O(n²)，并系统性地解决了结果去重这一核心难题。此解法是理解更复杂N数之和问题、掌握“有序数组上的双指针”这一经典范式的关键钥匙。作为鳄鱼Java的资深内容编辑，我将为你层层剥开这道经典题目的外衣，深入探究双指针解法背后的精妙逻辑与工程实现。
一、问题重述与挑战：为何它比“两数之和”更难？
问题描述：给定一个包含 n 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 a, b, c，使得 a + b + c = 0？请你找出所有满足条件且不重复的三元组。
关键挑战：
1. 寻找所有组合，而非单一解： 这与仅找一个答案的“两数之和”有本质区别。
2. 结果必须不重复： 这是本题最大的难点。例如，数组 `[-1, 0, 1, 1]`，`(-1, 0, 1)` 这个三元组只能出现一次，尽管有两个‘1’。
3. 时间复杂度要求高： 最直观的三重循环暴力法（O(n³)）在LeetCode上必然超时。
因此，我们需要一个系统性的、能同时高效搜索和自然去重的策略。LeetCode三数之和双指针解法正是为此而生。
二、算法核心思想：排序、固定、双指针收缩
该解法的精妙之处在于将一个三维搜索问题，降维为一系列有序数组上的二维搜索问题。其流程可分为四大步骤：
第一步：排序
对原数组进行升序排序。这是所有后续操作的基础，带来了两大决定性好处：
1. **为双指针高效搜索创造条件**： 在有序数组中，我们可以根据当前和与目标值的大小关系，智能地移动指针。
2. **为高效去重提供可能**： 相同的元素会相邻排列，使得我们可以在遍历中轻松跳过重复元素，避免生成重复的三元组。
第二步：外层循环，固定第一个数
遍历排序后的数组，将当前元素 `nums[i]` 作为三元组的第一个数（锚点）。
- **去重剪枝1**： 如果 `i > 0` 且 `nums[i] == nums[i-1]`，则直接 `continue`。因为以相同的数作为起点，找到的三元组必定重复。
第三步：内层循环，使用相向双指针寻找后两个数
对于固定的 `nums[i]`，我们需要在 `i` 右侧的区间 `[i+1, n-1]` 中找到两个数，使得它们的和等于 `target = 0 - nums[i]`。
- 初始化左指针 `left = i + 1`，右指针 `right = n - 1`。
- **双指针收缩逻辑（核心）**：
a. 计算当前和 `sum = nums[i] + nums[left] + nums[right]`。
b. 如果 `sum == 0`： 找到一组解，记录 `[nums[i], nums[left], nums[right]]`。随后，必须同时移动左右指针并跳过所有重复值（去重剪枝2和3）。
c. 如果 `sum < 0`： 说明总和太小，应将左指针 `left` 右移，以增大总和（因为数组有序）。
d. 如果 `sum > 0`： 说明总和太大，应将右指针 `right` 左移，以减小总和。
第四步：贯穿始终的细节去重
去重是此解法的灵魂，发生在三个层面：
1. **对第一个数去重**： 如前所述，在外层循环跳过重复的 `nums[i]`。
2. **对第二个数去重**： 当找到一组有效解后，在左指针右移的过程中，应使用 `while` 循环跳过所有与 `nums[left]` 相同的值。
3. **对第三个数去重**： 同样，在右指针左移的过程中，跳过所有与 `nums[right]` 相同的值。
这个LeetCode三数之和双指针解法的完整逻辑，是面试官考察候选人思维严密性的经典试金石。
三、Java代码实现与逐行解析
```java
class Solution {
public List
// 1. 排序：算法基石
Arrays.sort(nums);
// 2. 外层循环，固定第一个数
for (int i = 0; i < n - 2; i++) {
// 去重剪枝1：跳过重复的固定数
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 如果最小的三个数之和已大于0，后面无需再遍历（优化）
if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
break;
}
// 如果当前数加上最大的两个数仍小于0，说明当前数太小，跳过（优化）
if (nums[i] + nums[n - 2] + nums[n - 1] < 0) {
continue;
}
int target = -nums[i]; // 需要寻找的两数之和
int left = i + 1;
int right = n - 1;
// 3. 内层循环，双指针寻找
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 找到一组解
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重剪枝2：移动左指针，并跳过重复值
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// 去重剪枝3：移动右指针，并跳过重复值
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
// 正常移动指针，寻找下一组可能解
left++;
right--;
} else if (sum < target) {
// 总和太小，左指针右移
left++;
} else {
// 总和太大，右指针左移
right--;
}
}
}
return result;
}
}
<p>在鳄鱼Java社区的算法实战区，这段代码及其去重逻辑是每位参与者必须精通的“标准件”。</p>
<h2>四、复杂度分析与对比：为何双指针是优解？</h2>
<p><strong>时间复杂度：O(n²)**。
- 排序消耗 O(n log n)。<br>
- 外层循环 O(n)，内层双指针遍历 O(n)，嵌套后为 **O(n²)**。<br>
- 总时间复杂度由主导项 O(n²) 决定。</p>
<p><strong>空间复杂度：O(log n) 到 O(n)**。
- 取决于排序算法的实现。Java的 `Arrays.sort()` 对原始类型使用双轴快排，空间复杂度为 **O(log n)**；对对象使用TimSort，最坏情况为O(n)。<br>
- 除排序外，我们只使用了常数级别的额外变量。</p>
<p><strong>对比其他解法</strong>：</p>
<table border="1">
<tr><th>解法</th><th>时间复杂度</th><th>空间复杂度</th><th>核心挑战</th></tr>
<tr><td>三重循环暴力法</td><td>O(n³)</td><td>O(1)</td><td>无法处理大规模数据，去重极其复杂</td></tr>
<tr><td>哈希表法（类比两数之和）</td><td>O(n²)</td><td>O(n)</td><td>去重逻辑复杂，代码不易写对</td></tr>
<tr><td><strong>排序+双指针（本文核心）</strong></td><td><strong>O(n²)</strong></td><td><strong>O(log n)</strong></td><td><strong>结构清晰，去重自然高效</strong></td></tr>
</table>
<p>显然，<strong>双指针解法在时间复杂度上与哈希法持平，但在空间复杂度上更优，且其基于排序的去重逻辑在代码实现上更简洁、更不易出错</strong>，这是它在面试和工程实践中被广泛推崇的根本原因。</p>
<h2>五、关键细节深度剖析</h2>
<p><strong>1. 为什么排序是必要的？</strong><br>
排序不仅是为了使用双指针，更是实现<strong>系统性、无遗漏去重</strong>的唯一优雅途径。在不排序的数组中，检测 `nums[i]` 是否与前一个值重复需要O(n)的查找，而在有序数组中这是O(1)的比较。</p>
<p><strong>2. 双指针移动的正确性证明</strong><br>
当 `sum < target` 时，为什么只能右移 `left` 而不能左移 `right`？因为数组有序，`nums[left]` 是当前区间的最小值，`nums[right]` 是最大值。要增大总和，必须增大较小的加数（左指针的值），移动右指针只会让总和更小。反之亦然。</p>
<p><strong>3. 去重代码的精确位置</strong><br>
去重操作 `while (left < right && nums[left] == nums[left+1])` 必须放在<strong>找到一组有效解之后、常规移动指针之前</strong>。如果放在计算`sum`之前，会错误地跳过可能形成不同三元组的相同值（例如，[-2, 0, 1, 1]，第一个1和第二个1与-2组合的目标值不同）。</p>
<p><strong>4. 早期剪枝优化</strong><br>
代码中新增的 `if (nums[i] + nums[i+1] + nums[i+2] > 0) break;` 和 `if (nums[i] + nums[n-2] + nums[n-1] < 0) continue;` 是锦上添花的优化。它们利用了排序后的单调性，提前终止不可能产生结果的循环，在数据量大时能显著提升性能。</p>
<h2>六、举一反三：从三数之和到N数之和</h2>
<p>掌握<strong>LeetCode三数之和双指针解法</strong>的范式后，你可以将其推广至更通用的问题：</p>
<p><strong>1. 四数之和（LeetCode 18）</strong>： 在三数之基础上，再增加一层外层循环，固定第一个数，内层转化为三数之和问题。核心依然是排序、双层固定、内层双指针，以及多层级的去重。<br>
<strong>2. 最接近的三数之和（LeetCode 16）</strong>： 框架完全一致，只需将判断条件从 `sum == target` 改为跟踪 `Math.abs(sum - target)` 的最小值，并相应调整指针移动逻辑。<br>
<strong>3. 更通用的递归回溯解法</strong>： 对于N数之和，可以设计一个递归函数，每次递归固定一个数，将问题规模减一，直到转化为两数之和再用双指针解决。这体现了<strong>降维</strong>和<strong>分治</strong>的思想。</p>
<p>在鳄鱼Java社区的项目架构讨论中，这种“先排序预处理，再通过多指针协同搜索”的思想，也能在解决某些数据处理和查询优化问题时带来启发。</p>
<h2>总结与思考</h2>
<p><strong>LeetCode三数之和双指针解法</strong>是一道集大成的算法练习题。它融合了排序预处理、双指针技巧、去重逻辑和早期剪枝，完整地展示了一个高效算法从构思到实现的思维链条。</p>
<p>现在，请你反思：你是否真正理解了去重代码的每一行及其放置位置背后的原因？你是否能清晰地向他人解释为什么双指针的移动规则是正确且不会遗漏解的？当你面对“四数之和”时，能否自信地搭建出类似的解构框架？算法的学习，其精髓不在于背诵代码，而在于掌握这种将复杂问题分解、转化、并系统化解决的思维能力。如果你想在算法之路上走得更远，欢迎持续深入鳄鱼Java社区的算法专栏，这里将有更多经典问题等待与你一同拆解、精研。</p>
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
