LeetCode 18. 四数之和
目录
题目描述
✅ 18. 四数之和
题意分析
要找的是所有互不重复的四元组，四个元素取自互不相同的下标，且四数之和恰好等于
target。四元组内部的先后顺序、以及答案里各四元组之间的顺序都不作要求，但同一组数值只能出现一次。
约束给了两个信号：一是数组长度只有 200 量级，容忍 $O(n^3)$ 级别的枚举；二是nums[i]与target都可以取到 32 位整型的两端，四个这样的数相加会冲出 32 位。
边界要事先想清楚：长度不足 4 时答案为空；数组可能整片都是相同值；「不重复」是按数值判定而不是按下标判定的，所以[0,0,0,0]只能产出一组答案。
解法：排序 + 双层固定 + 双指针
核心思路
四重枚举需要 $O(n^4)$。先排序后固定前两个数
nums[i]、nums[j]，问题就降为在右侧有序区间中寻找目标两数，可用双指针把后两层从 $O(n^2)$ 降到 $O(n)$；排序还让相同值相邻，去重无需额外集合。对固定的
(i,j)，未检查的候选始终位于[left,right]。若四数和偏小，那么当前left与区间内任意右端搭配都不会更大到命中目标，可以排除它并右移；和偏大时同理排除right。命中后同时移动两端并跳过相同值。去重必须分层进行：
i只与上一轮i比，j只在当前i下与上一轮j比，命中后再跳过左右指针刚使用的值。这样每组数值只产生一次，又不会误删需要使用多个相同元素的合法答案。求和使用 64 位整数，避免四个 32 位数相加溢出。
解题步骤
- 将数组升序排序，使双指针移动和相邻去重都有依据。
- 枚举
i，若i > 0 && nums[i] == nums[i-1]则跳过。- 枚举
j，仅当j > i+1 && nums[j] == nums[j-1]时跳过；j == i+1是本层第一次使用该值，不能去重。- 在
[j+1,n-1]放置双指针。用 64 位计算总和：偏小移动left，偏大移动right。- 命中时记录四元组，同时收缩两端，再分别跳过与刚使用值相同的元素。
[-2,-1,0,0,1,2]、target=0最终得到[-2,-1,1,2]、[-2,0,0,2]、[-1,0,0,1]；[0,0,0,0]中相同值可以占四个位置，但答案只输出一次。
代码实现
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
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 计算四数和，避免极值输入溢出。
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
import "sort"
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
res := make([][]int, 0)
n := len(nums)
for i := 0; i < n-3; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < n-2; j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
left := j + 1
right := n - 1
for left < right {
sum := int64(nums[i]) + int64(nums[j]) + int64(nums[left]) + int64(nums[right])
if sum == int64(target) {
res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if sum < int64(target) {
left++
} else {
right--
}
}
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n^3)$。排序为 $O(n \log n)$，两层枚举与一轮线性双指针为 $O(n^3)$。
- 空间复杂度：忽略返回结果，指针部分为 $O(1)$；计入语言排序实现的调用栈通常为 $O(\log n)$。
关键点总结
- 排序同时解决双指针的单调性和按数值去重，是 nSum 问题的基础。
- 去重是“同一层不重复选同一个值”，不是全局禁止重复值；否则
[0,0,0,0]会被误删。- 命中后左右指针都要移动，并分别越过刚使用值的重复项。
- 面试中要主动说明双指针为何不会漏解，以及求和为什么必须转成 64 位。
易错点总结
- 用 32 位整数求四数和：极值输入会溢出，导致指针移动方向错误。
j去重漏掉j > i+1：[0,0,0,0]会把本层第一个 0 也跳过，丢失合法答案。- 命中后不跳过左右重复值：
[2,2,2,2,2]、target=8会重复输出同一四元组。- 循环写成
left <= right：当两指针重合时会重复使用同一下标。- 未排序就移动双指针：和的变化失去单调性，移动任何一端都可能漏解。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 15. 三数之和 | 中等 | 少固定一层，去重只需处理三个位置 |
| 16. 最接近的三数之和 | 中等 | 求最接近而非相等，无需去重 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 输入已有序，直接双指针并返回下标 |
| 259. 较小的三数之和 | 中等 | 统计满足小于关系的组合数而非列举 |
| 611. 有效三角形的个数 | 中等 | 固定最长边后用双指针批量计数 |
| 1099. 小于 K 的两数之和 | 简单 | 求不超过上界的最大两数和 |
| LCR 006. 两数之和 II - 输入有序数组 | 简单 | 有序两数之和的下标版本 |
| LCR 007. 三数之和 | 中等 | 三数之和换编号，去重要求完全一致 |
| 剑指 Offer 57. 和为s的两个数字 | 简单 | 有序数组中任取一组解即可 |
| 面试题 16.24. 数对和 | 中等 | 无序数组配对，可用哈希代替排序 |