登录一次彻底搞懂 Four Sum（四数之和）：排序 + 双指针的终极形态
LeetCode 18｜中等
核心思想：排序 + 枚举 + 双指针 + 去重
本文目标：让你不仅写得出，还能一眼看穿这一类题
一、题目描述
给定一个整数数组 nums 和一个目标值 target，判断数组中是否存在 四个不同下标 的元素，使得它们的和等于 target，并返回所有 不重复的四元组。
示例：
nums = [1,0,-1,0,-2,2], target = 0
输出：
[
[-2,-1,1,2],
[-2,0,0,2],
[-1,0,0,1]
]
二、暴力解法为什么行不通？
最直观的思路是四重循环：
for a
for b
for c
for d
时间复杂度：
O(n^4)
当 n 稍微一大，直接超时。这也是 Four Sum 这道题存在的意义：逼你系统性掌握降维思路。
三、核心优化思路：降维 + 双指针
观察等式：
a + b + c + d = target
我们可以把它拆成：
(a + b) + (c + d) = target
思路就非常清晰了：
- 固定前两个数
a、b - 剩下的
c + d用 双指针（Two Sum） 解决 - 通过排序解决双指针和去重问题
这正是 Two Sum → Three Sum → Four Sum 的统一解题套路。
四、完整 Java 实现
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
if (n < 4) return res;
Arrays.sort(nums);
// 第一层枚举 a
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 第二层枚举 b
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;
// 双指针找 c + d
while (left < right) {
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]
));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
五、为什么一定要排序？
排序在这道题中起到了决定性作用：
- 让双指针成为可能
- 为去重提供天然条件
- 让结果具备统一顺序，避免重复解
可以说：没有排序，Four Sum 根本写不干净。
六、去重逻辑是整道题的灵魂
Four Sum 的难点不在算法，而在 不重不漏。
1. 第一层去重（a）
if (i > 0 && nums[i] == nums[i - 1]) continue;
避免相同的 a 被重复枚举。
2. 第二层去重（b）
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
注意这里是 j > i + 1，而不是 j > 0，这是很多人第一次写时会踩的坑。
3. 双指针去重（c、d）
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
只在 找到一个合法解之后 去重，这是关键。
七、为什么 sum 要用 long？
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
原因只有一个：防止整数溢出。
-
nums[i]可能是10^9 - 四个 int 相加很容易溢出
这是 Four Sum 的经典细节坑，面试和刷题都很爱考。
八、时间与空间复杂度分析
时间复杂度：
O(n^3)
- 两层枚举：O(n²)
- 内层双指针：O(n)
空间复杂度：
O(1)（不计结果集）
九、Four Sum 的本质总结
这一类题的本质其实非常统一：
| 题目 | 固定元素个数 | 剩余解法 |
|---|---|---|
| Two Sum | 0 | 双指针 / 哈希 |
| Three Sum | 1 | 双指针 |
| Four Sum | 2 | 双指针 |
一句话总结：
固定 k − 2 个数，把 k Sum 问题降维为 Two Sum。
