LeetCode 15. 三数之和
题目描述
✅ 15. 三数之和
题意分析
从数组中选出三个不同位置的元素，使它们的和等于
0，返回所有满足条件的数值组合。不同位置的元素可以有相同的值，同一个位置不能使用两次。答案按数值组合去重：即使使用了不同下标，只要选出的三个数相同，就只保留一组。三元组内部及各组之间的顺序不限；没有符合条件的组合时返回空结果。
解法：排序 + 双指针
核心思路
[!blue]
先将数组从小到大排序，再固定第一个数
nums[i]，在它右侧寻找和为-nums[i]的两个数。让left从i + 1开始，right从数组末尾开始，既能避免复用同一下标，也能让每组数只按从小到大的顺序被找到。如果三数之和小于
0，说明当前左端的数太小：即使搭配右侧最大的候选值也不够，因此可以排除这个左端点，将left右移。如果和大于0，说明当前右端的数太大：即使搭配左侧最小的候选值也超出，因此将right左移。这样每次都能排除不可能组成答案的候选，不会漏解。和等于
0时记录答案，再让两侧指针跳过与当前值相同的元素，寻找新的组合。外层固定数也要跳过重复值，避免再次找出同一批答案。若固定数已经大于0，它右侧的数也都为正，可以直接结束。
解题步骤
- 将数组升序排序，枚举第一个数的位置
i，为右侧保留至少两个元素。- 若
nums[i] > 0，结束枚举；若它与上一次固定数相同，跳过本轮。- 令
left = i + 1、right = n - 1，在left < right时计算三数之和。- 和小于
0就右移left，大于0就左移right；等于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;
int 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];
int rightValue = nums[right];
while (left < right && nums[left] == leftValue) {
left++;
}
while (left < right && nums[right] == rightValue) {
right--;
}
}
}
}
return result;
}
}
import "sort"
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(n)$，Go
sort.Ints为 $O(\log n)$ 栈空间。
关键点总结
[!green]
- 排序让指针可以按和的大小单向移动。
- 去重分两层：固定数去重、命中后三元组去重。
nums[i] > 0后不可能再得到和为 0 的三元组。
易错点总结
[!yellow]
- 固定数重复时未跳过，导致重复答案。
- 命中后未移动或去重指针，导致重复结果甚至死循环。
- 双指针从
i + 1开始，避免重复使用同一元素。nums[i] > 0时后续三数和也为正，可直接break；使用continue不影响结果，但会继续做无用的外层遍历。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 16. 最接近的三数之和 | 中等 | 同样排序后固定一项并对撞指针，原题找最接近的和，本题输出恰好为0的全部不重复组合。 |
| 18. 四数之和 | 中等 | 把固定一个数扩展为固定两个数，内层仍复用双指针和重复值处理。 |
| 259. 较小的三数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题固定一个数寻找零和三元组，该题满足阈值时批量累计指针对数。 |
| 611. 有效三角形的个数 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题固定一个数寻找零和三元组，该题把三角不等式转为两数和比较。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！