题目描述
LeetCode 15. 三数之和
给定一个整数数组 nums，判断是否存在三个元素 a, b, c，使得 a + b + c = 0？
找出所有和为 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]]学习历程（从暴力到优化）
第一步：分析暴力解法
第一反应：三重循环枚举所有三元组
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
if nums[i] + nums[j] + nums[k] == 0:
记录结果复杂度分析:
时间复杂度：O(n³)
空间复杂度：O(1)（不考虑结果存储）
问题：
太慢了，n=3000时根本跑不完
去重很麻烦，需要额外处理
第二步：联想两数之和
思考：如果只有两数之和（找 a + b = target），有什么更好的做法？
方案一：哈希表（O(n)时间）
遍历数组，把每个数存入HashSet
对于当前数 x，检查 target - x 是否在Set中
方案二：排序+双指针（O(nlogn)时间）
先排序
左指针指向开头，右指针指向结尾
根据 sum 和 target 的大小关系移动指针
第三步：关键洞察——降维思想
三数之和 a + b + c = 0 可以变形为：b + c = -a
策略：
固定第一个数
a（遍历数组）在剩下的区间找两数之和等于
-a这就转化成了「两数之和」问题！
复杂度预估：
固定第一个数：O(n)
每次找两数之和：O(n)（双指针）
总复杂度：O(n²)
比暴力 O(n³) 提升了一个数量级！
第四步：排序+双指针详解
为什么要先排序？
排序后可以使用双指针技巧，而且重复数字会相邻，方便去重。
双指针怎么工作？
假设数组已排序：[-4, -1, -1, 0, 1, 2]
例：找两数之和 = 0
初始：L=0(-4), R=5(2)
sum = -4 + 2 = -2 < 0
→ sum太小了，需要变大，L右移（让负数变小）
L=1(-1), R=5(2)
sum = -1 + 2 = 1 > 0
→ sum太大了，需要变小，R左移
L=1(-1), R=4(1)
sum = -1 + 1 = 0 ✓ 找到了！指针移动规则：
sum < target：L右移（需要更大的数）sum > target：R左移（需要更小的数）sum == target：找到了！L++ 且 R--（继续找其他组合）
第五步：去重处理（难点）
排序后重复数字相邻，比如：[-1, -1, -1, 0, 1, 2]
三个去重点：
固定的数去重：
if i > 0 && nums[i] == nums[i-1] { continue; // 跳过重复的固定值 }左指针去重：
while (L < R && nums[L] == nums[L+1]) L++;右指针去重：
while (L < R && nums[R] == nums[R-1]) R--;
完整代码实现（Java）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 1. 排序（O(nlogn)）
Arrays.sort(nums);
int n = nums.length;
// 2. 固定第一个数
for (int i = 0; i < n - 2; i++) {
// 剪枝：如果当前数已经大于0，后面的都大于0，不可能和为0
if (nums[i] > 0) {
break;
}
// 去重：跳过重复的固定值
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 3. 双指针找另外两个数
int target = -nums[i]; // 需要找的两数之和
int left = i + 1; // 左指针
int right = n - 1; // 右指针
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
// 太小了，左指针右移
left++;
} else if (sum > target) {
// 太大了，右指针左移
right--;
} else {
// 找到了！
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--;
}
}
}
return result;
}
// 测试
public static void main(String[] args) {
ThreeSum solution = new ThreeSum();
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = solution.threeSum(nums);
System.out.println("结果：" + result);
// 输出：[[-1, -1, 2], [-1, 0, 1]]
}
}复杂度分析
关键总结
解题模板（排序+双指针）
1. 排序数组
2. 固定一个数（遍历）
3. 双指针在剩余区间查找
4. 根据sum大小移动指针
5. 注意三个地方的去重类似题目
面试技巧
先讲暴力解：展示思路完整性，至少能得部分分
引导到优化：面试官问"能不能优化"时，提排序+双指针
手写去重逻辑：这是考察重点，要写得干净利落
分析复杂度：证明你的解法是正确的最优解
易错点复盘
忘记排序：双指针必须在有序数组上工作
去重逻辑漏了：三个地方都要去重（固定值、左指针、右指针）
指针越界：
left < right别写成left <= rightsum计算错误：注意负数的情况，比如
-1 + 2 = 1不是-3