LeetCode 15. 三数之和
目录
题目描述
✅ 15. 三数之和
题意分析
题目要求从数组
nums中选出三个下标互不相同的元素，使它们的和为 0，并返回所有互不重复的三元组。这里需要分清两个概念：三个元素必须来自不同下标，但它们的数值可以相同；即使不同的下标组合得到相同的三个数，答案中也只能保留一份。
例如，
nums = [-1,0,1,2,-1,-4]中有两个值为-1的元素，因此可以选出[-1,-1,2]。而对于[-1,0,1]，虽然任意一个-1都能与0、1组成答案，但它们对应的数值组合相同，所以最终只能返回一次。因此，本题不仅要找出所有和为 0 的三元组，还要在搜索过程中避免产生重复答案。
直接枚举三个下标需要 $O(n^3)$ 的时间。可以借鉴两数之和的思路：先固定一个数
nums[i]，再在它右侧寻找两个数，使它们的和等于-nums[i]。为了高效完成搜索并方便去重，可以先对数组排序，再使用双指针。排序解决了两个问题：固定
nums[i]后，左右指针的移动与三数之和的变化有了明确关系；同时，相同的数值会聚在一起，只需跳过相邻的重复值，就能避免生成重复三元组。相比之下，使用哈希表时还要额外设计结果去重逻辑，因此排序加双指针更适合本题。去重需要处理两个位置：外层跳过重复的固定数；找到答案后，内层跳过左右指针指向的重复值。这样才能保证最终结果既不遗漏，也不重复。
排序后还可以提前结束：当
nums[i] > 0时，右侧元素也都大于 0，三数之和不可能等于 0，因此可以直接退出循环。边界情况包括：数组长度小于 3 时没有答案；对于
[0,0,0,0]，最终只能返回一个[0,0,0]。
解法：排序 + 双指针
核心思路
先排序，再枚举第一个数
nums[i]，用左右指针在其右侧寻找和为-nums[i]的两个数。和偏小时右移左指针，和偏大时左移右指针。固定数和命中后的左右指针都要去重，保证结果不重复。
解题步骤
- 升序排序数组。
- 枚举
i；跳过重复固定数，nums[i] > 0时结束。- 令
left = i + 1、right = n - 1。- 根据三数之和移动指针；等于 0 时记录答案，并跳过两侧重复值。
代码实现
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
int leftValue = nums[left], rightValue = nums[right];
while (left < right && nums[left] == leftValue) {
left++;
}
while (left < right && nums[right] == rightValue) {
right--;
}
}
}
}
return result;
}
}
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := make([][]int, 0)
for i := 0; i < len(nums)-2; i++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum < 0 {
left++
} else if sum > 0 {
right--
} else {
result = append(result, []int{nums[i], nums[left], nums[right]})
leftValue, rightValue := nums[left], nums[right]
for left < right && nums[left] == leftValue {
left++
}
for left < right && nums[right] == rightValue {
right--
}
}
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n^2)$；排序为 $O(n \log n)$，双指针总计 $O(n^2)$。
- 空间复杂度：忽略返回结果，Java 排序最坏 $O(\log n)$，Go
sort.Ints为 $O(\log n)$ 栈空间。
关键点总结
- 排序让指针可以按和的大小单向移动。
- 去重分两层：固定数去重、命中后三元组去重。
nums[i] > 0后不可能再得到和为 0 的三元组。
易错点总结
- 固定数重复时未跳过，导致重复答案。
- 命中后未移动或去重指针，导致重复结果甚至死循环。
- 双指针从
i + 1开始，避免重复使用同一元素。nums[i] > 0应break，不是continue。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | nSum 的起点，要求返回下标所以用哈希而非排序双指针 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 输入已有序，本题内层双指针的裸版本 |
| 16. 最接近的三数之和 | 中等 | 目标从「等于 0」变成「最接近」，无需去重但要边移动边维护最优差 |
| 18. 四数之和 | 中等 | 再套一层固定数，去重变成三层，还要注意四数相加的溢出 |
| 259. 较小的三数之和 | 中等 | 求和小于目标的组合数量，条件满足时一次性累加 right - left
|
| 611. 有效三角形的个数 | 中等 | 排序后固定最大边，双指针统计满足两边之和大于第三边的对数 |
| 1099. 小于 K 的两数之和 | 简单 | 双指针在移动中维护最优解，是 259 的两数版本 |
| LCR 007. 三数之和 | 中等 | 与本题同题，可直接套用 |
| LCR 006. 两数之和 II - 输入有序数组 | 简单 | 与 167 同题 |
| 剑指 Offer 57. 和为s的两个数字 | 简单 | 有序数组两数之和，返回值本身而非下标 |
| 面试题 16.24. 数对和 | 中等 | 要求返回所有数对，可用排序双指针也可用哈希计数 |