LeetCode 18中等双指针
四数之和 图解题解
四个数之和：排序后两层循环各固定一个，内层对撞指针一趟扫，O(n⁴) 直接降到 O(n³)。
先排好序，外面两层循环各锁定一张牌，内层再从剩余两端往中间夹：四张合计太大就把右端换小的，太小就把左端换大的，凑中目标就记下来继续走。比四重穷举少了一整层，重复值也靠「相邻跳过」一口气去掉。
这道题到底在问什么
在数组里找出所有不重复的四元组，使四个数之和等于 target。
- nums, target
- [1,0,-1,0,-2,2], 0
- 输出
- [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
先想最直接的笨办法
暴力四重循环是 O(n⁴)，太慢。排序之后固定 i 和 j，问题就缩成「在右边找两个数，让它们的和等于 target 减去这两个固定值」，再用对撞双指针一趟扫完，整体降到 O(n³)。（动画第 3 步）
最优解：一步一步想明白
- 3暴力四重循环是 O(n⁴)，太慢。排序之后固定 i 和 j，问题就缩成「在右边找两个数，让它们的和等于 target 减去这两个固定值」，再用对撞双指针一趟扫完，整体降到 O(n³)。
- 4[-2,-1,0,0,1,2]原数组 [1,0,-1,0,-2,2] 先排序，变成 [-2,-1,0,0,1,2]。有序之后才能用对撞双指针，也方便靠「相邻相同」跳过重复值去重。
- 5l=2, r=5 · 需要凑出 3固定前两个数：i=0 是 −2，j=1 是 −1。剩下要在右边凑出 0 减 −2 减 −1，也就是 3。左指针 l 在下标 2，右指针 r 在下标 5，当前和是 0 加 2 等于 2，比 3 小，把左指针右移换个更大的数。
- 6l=3, r=5 · 和=2 还是太小左指针移到下标 3，可它也是 0，和还是 2，仍然小于 3。继续把左指针右移。
- 7l=4, r=5 · 和=3 ✓左指针移到下标 4（值 1），和等于 1 加 2 等于 3，正好凑齐！四个数 −2、−1、1、2 加起来是 0，记录第一个四元组 [−2,−1,1,2]。
- 8l=5, r=4 · 本轮结束命中后左指针右移、右指针左移，并跳过相邻相同值。现在左指针到 5、右指针到 4，两边交叉，固定 j=1 这一轮就结束了。已收下 [−2,−1,1,2]。
- 9l=3, r=5 · 需要凑出 2j 推进到下标 2（值 0），i 还是 −2。这回要凑出 0 减 −2 减 0 等于 2。左指针 l=3、右指针 r=5，和就是 0 加 2 等于 2，一上来就命中！
- 10l=4, r=4 · 交叉结束记录第二个四元组 [−2,0,0,2]。左右指针双移后都到下标 4，相遇，j=2 这一轮也结束。
- 11nums[3]==nums[2]=0 → continuej 推到下标 3，值还是 0，和上一个 j 完全一样。再做一遍只会得到和刚才重复的四元组，所以直接跳过——这就是 j 层去重，少了它答案就会出现重复。
- 12l=3, r=5 · 需要凑出 1i 推进到下标 1（值 −1），j=2 是 0。这次要凑出 0 减 −1 减 0 等于 1。当前和是 0 加 2 等于 2，比 1 大，这回换成右指针左移、换个更小的数。
- 13l=3, r=4 · 和=1 ✓右指针左移到下标 4（值 1），和是 0 加 1 等于 1，命中！记录第三个四元组 [−1,0,0,1]。
- 14后续 i/j 凑不出 0命中后双移交叉，本轮结束。再往后 i 取 0 或更大时，最小四个数的和都已经大于 0，凑不出目标，遍历到此为止。
- 15ans = [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]整趟扫描收齐三个四元组：[−2,−1,1,2]、[−2,0,0,2]、[−1,0,0,1]。这一遍把「和小了右移左指针、和大了左移右指针、命中记录、各层去重」四种情况都演了一遍。
- 18两数之和是对撞双指针；三数之和在外面套一层固定；四数之和再套一层。规律就是：K 数之和每多一个数就多固定一层，最里面那层永远是左右指针对撞。
- 23把这题练到能默写后，再迁移到同类：LC15 三数之和（少一层固定）、LC16 最接近的三数之和（把相等判断改成记录最小差值）、K 数之和通用递归版。练完不妨找 AI 助教抽查你的去重逻辑，或去通关训练里实战一遍。
⚠️ 容易写错的地方
✗ 错：i 和 j 的去重条件写成一样
✓ 对：i 层判 i 大于 0，j 层判 j 大于 i+1
j 的去重起点是 i+1 不是 0；写成 j 大于 0 会把每段的第一个 j 也错误跳掉，漏解
✗ 错：命中后只移动一个指针
✓ 对：命中后 l 右移且 r 左移，再各自跳过相邻相同值
只移一边会卡在原地反复命中同一组，产生重复四元组
✗ 错：C++/Java 直接用 int 相加四个数
✓ 对：先强转 long：(long)nums[i]+nums[j]+nums[l]+nums[r]
四个 int 之和可达约 40 亿，超出 int 上限会溢出成负数，判断全错
完整代码（Python / C++ / Java）
Python
class Solution:
def fourSum(self, nums, target):
nums.sort()
n = len(nums)
ans = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
l, r = j + 1, n - 1
while l < r:
s = nums[i] + nums[j] + nums[l] + nums[r]
if s == target:
ans.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif s < target:
l += 1
else:
r -= 1
return ansC++
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i + 3 < n; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j = i + 1; j + 2 < n; j++) {
if (j > i + 1 && nums[j] == nums[j-1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long s = (long)nums[i] + nums[j] + nums[l] + nums[r];
if (s == target) {
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
l++; r--;
while (l < r && nums[l] == nums[l-1]) l++;
while (l < r && nums[r] == nums[r+1]) r--;
} else if (s < target) l++;
else r--;
}
}
}
return ans;
}
};Java
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i + 3 < n; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j = i + 1; j + 2 < n; j++) {
if (j > i + 1 && nums[j] == nums[j-1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long s = (long)nums[i] + nums[j] + nums[l] + nums[r];
if (s == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
l++; r--;
while (l < r && nums[l] == nums[l-1]) l++;
while (l < r && nums[r] == nums[r+1]) r--;
} else if (s < target) l++;
else r--;
}
}
}
return ans;
}
}套路模板 · K 数之和双指针骨架
# 四数之和挖空骨架：把每个 ___ 填上就能跑
nums.sort()
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]: continue # ___ i 层去重
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]: continue # ___ j 层去重
l, r = j+1, n-1
while l < r:
s = nums[i]+nums[j]+nums[l]+nums[r]
if s == target: 记录; l+=1; r-=1; 跳重 l; 跳重 r
elif s < target: l += 1 # 和偏小 → 左指针右移
else: r -= 1 # 和偏大 → 右指针左移// 四数之和挖空骨架
sort(nums.begin(), nums.end());
for (int i = 0; i+3 < n; i++) {
if (i > 0 && nums[i]==nums[i-1]) continue; // i 层去重
for (int j = i+1; j+2 < n; j++) {
if (j > i+1 && nums[j]==nums[j-1]) continue; // j 层去重
int l = j+1, r = n-1;
while (l < r) {
long s = (long)nums[i]+nums[j]+nums[l]+nums[r]; // 必须 long
if (s == target) { 记录; l++; r--; 跳重 l; 跳重 r; }
else if (s < target) l++; // 偏小右移 l
else r--; // 偏大左移 r
}
}
}// 四数之和挖空骨架
Arrays.sort(nums);
for (int i = 0; i+3 < n; i++) {
if (i > 0 && nums[i]==nums[i-1]) continue; // i 层去重
for (int j = i+1; j+2 < n; j++) {
if (j > i+1 && nums[j]==nums[j-1]) continue; // j 层去重
int l = j+1, r = n-1;
while (l < r) {
long s = (long)nums[i]+nums[j]+nums[l]+nums[r]; // 必须 long
if (s == target) { 记录; l++; r--; 跳重 l; 跳重 r; }
else if (s < target) l++; // 偏小右移 l
else r--; // 偏大左移 r
}
}
}复杂度
时间复杂度
O(n³)
排序 O(n log n)；i 层 O(n) × j 层 O(n) × 内层双指针 O(n) = O(n³)
空间复杂度
O(1)
不计答案数组，只用 i/j/l/r 常数个指针变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 四数之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能推广到 K 数之和吗？+
可以，写成递归：当 K 大于 2，固定一个数后递归求 K−1 数之和；K 等于 2 时退化成对撞双指针。整体时间复杂度 O(n^(K−1))。
为什么 C++/Java 要用 long，Python 却不用？+
C++/Java 的 int 是 32 位，最大约 21 亿，四个大数相加可能超出范围。Python 整数是任意精度、没有上限，所以不会溢出。
一共有几处去重？分别在哪？+
四处。i 层：i 大于 0 且 nums[i] 等于 nums[i−1] 就跳；j 层：j 大于 i+1 且 nums[j] 等于 nums[j−1] 就跳；命中后移动 l 和 r 时，也各自跳过相邻相同值。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。