LeetCode 18中等双指针
四数之和 图解题解
四个数之和：排序后两层循环各固定一个，内层对撞指针一趟扫，O(n⁴) 直接降到 O(n³)。
先排好序，外面两层循环各锁定一张牌，内层再从剩余两端往中间夹：四张合计太大就把右端换小的，太小就把左端换大的，凑中目标就记下来继续走。比四重穷举少了一整层，重复值也靠「相邻跳过」一口气去掉。
这道题到底在问什么
给定数组 nums 和目标值 target，返回所有和为 target 的不重复四元组。
- 输入
- nums=[1,0,-1,0,-2,2], target=0
- 输出
- [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
先想最直接的笨办法
整趟扫完，i/j 两层固定 + l/r 对撞，去重后收齐 4 个四元组：[-2,-1,0,3]、[-2,-1,1,2]、[-2,0,0,2]、[-1,0,0,1]。两层固定各约 n 次、最内层对撞线性，总复杂度 O(n³)，比暴力四重循环 O(n⁴) 少一个量级。（动画第 28 步）
最优解：一步一步想明白
- 3记住这条「排序 + 双层固定 + 对撞双指针」，下面每一帧都在套它。
- 4第一步永远是排序：[1,0,-1,0,-2,2,3] 排成 [-2,-1,0,0,1,2,3]。排好序，指针才能靠「和的大小」判断该往哪移、相邻相同值才好去重。
- 5固定前两个数：i 指下标 0（值 -2）、j 指下标 1（值 -1）。剩下要在 j 右边凑出 0 − -2 − -1 = 3。左指针 l 摆在下标 2、右指针 r 摆在下标 6，开始对撞。
- 6正好凑齐！-2+-1+0+3 = 0，记录四元组 [-2,-1,0,3]（绿色高亮）。命中后 l 右移、r 左移继续找别的组合。
- 7命中后 l、r 内移，跳过和刚才重复的值（左边），现在 l 到下标 4、r 到下标 5，两边还没相遇，继续对撞。
- 8正好凑齐！-2+-1+1+2 = 0，记录四元组 [-2,-1,1,2]（绿色高亮）。命中后 l 右移、r 左移继续找别的组合。
- 9命中后 l、r 内移，现在 l、r 相遇，这一对 i、j 下的内层搜索结束，回去推进 j 或 i。
- 10固定前两个数：i 指下标 0（值 -2）、j 指下标 2（值 0）。剩下要在 j 右边凑出 0 − -2 − 0 = 2。左指针 l 摆在下标 3、右指针 r 摆在下标 6，开始对撞。
- 11四数之和 = 1 > 0，太大了。把右指针左移一格到下标 5（值 2），让和变小。
- 12正好凑齐！-2+0+0+2 = 0，记录四元组 [-2,0,0,2]（绿色高亮）。命中后 l 右移、r 左移继续找别的组合。
- 13命中后 l、r 内移，现在 l、r 相遇，这一对 i、j 下的内层搜索结束，回去推进 j 或 i。
- 14固定前两个数：i 指下标 0（值 -2）、j 指下标 4（值 1）。剩下要在 j 右边凑出 0 − -2 − 1 = 1。左指针 l 摆在下标 5、右指针 r 摆在下标 6，开始对撞。
- 15四数之和 = 4 > 0，太大了。把右指针左移一格到下标 5（值 2），让和变小。
- 16固定前两个数：i 指下标 1（值 -1）、j 指下标 2（值 0）。剩下要在 j 右边凑出 0 − -1 − 0 = 1。左指针 l 摆在下标 3、右指针 r 摆在下标 6，开始对撞。
- 17四数之和 = 2 > 0，太大了。把右指针左移一格到下标 5（值 2），让和变小。
- 18四数之和 = 1 > 0，太大了。把右指针左移一格到下标 4（值 1），让和变小。
- 19正好凑齐！-1+0+0+1 = 0，记录四元组 [-1,0,0,1]（绿色高亮）。命中后 l 右移、r 左移继续找别的组合。
- 20命中后 l、r 内移，现在 l、r 相遇，这一对 i、j 下的内层搜索结束，回去推进 j 或 i。
- 21固定前两个数：i 指下标 1（值 -1）、j 指下标 4（值 1）。剩下要在 j 右边凑出 0 − -1 − 1 = 0。左指针 l 摆在下标 5、右指针 r 摆在下标 6，开始对撞。
- 22四数之和 = 5 > 0，太大了。把右指针左移一格到下标 5（值 2），让和变小。
- 23固定前两个数：i 指下标 2（值 0）、j 指下标 3（值 0）。剩下要在 j 右边凑出 0 − 0 − 0 = 0。左指针 l 摆在下标 4、右指针 r 摆在下标 6，开始对撞。
- 24四数之和 = 4 > 0，太大了。把右指针左移一格到下标 5（值 2），让和变小。
- 25四数之和 = 3 > 0，太大了。把右指针左移一格到下标 4（值 1），让和变小。
- 26固定前两个数：i 指下标 2（值 0）、j 指下标 4（值 1）。剩下要在 j 右边凑出 0 − 0 − 1 = -1。左指针 l 摆在下标 5、右指针 r 摆在下标 6，开始对撞。
- 27四数之和 = 6 > 0，太大了。把右指针左移一格到下标 5（值 2），让和变小。
- 28整趟扫完，i/j 两层固定 + l/r 对撞，去重后收齐 4 个四元组：[-2,-1,0,3]、[-2,-1,1,2]、[-2,0,0,2]、[-1,0,0,1]。两层固定各约 n 次、最内层对撞线性，总复杂度 O(n³)，比暴力四重循环 O(n⁴) 少一个量级。
⚠️ 容易写错的地方
✗ 错：不排序就用双指针
✓ 对：必须先排序
指针靠「和的大小」决定移哪边、相邻相同值才好去重
✗ 错：i/j 去重判断位置写错
✓ 对：i 用 i>0、j 用 j>i+1
判断条件不对会漏解或留重复四元组
✗ 错：四个 int 相加爆 int
✓ 对：C++/Java 累加用 long
target 可能很大，四个边界值相加会溢出
完整代码（Python / C++ / Java）
Python
def fourSum(nums, target):
nums.sort(); n = len(nums); res = []
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:
res.append([nums[i], nums[j], nums[l], nums[r]])
l += 1; r -= 1
while l < r and nums[l] == nums[l-1]: l += 1 # l 去重
while l < r and nums[r] == nums[r+1]: r -= 1 # r 去重
elif s < target: l += 1
else: r -= 1
return resC++
vector<vector<int>> fourSum(vector<int>& nums, int target){
sort(nums.begin(), nums.end()); int n = nums.size();
vector<vector<int>> res;
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 l = j + 1, r = n - 1;
while(l < r){
long s = (long)nums[i]+nums[j]+nums[l]+nums[r]; // long 防溢出
if(s == target){
res.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 res;
}Java
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums); int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // i 去重
for (int j = i + 1; j < n - 2; 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]; // 防溢出
if (s == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
l++; r--;
while (l < r && nums[l] == nums[l-1]) l++; // l 去重
while (l < r && nums[r] == nums[r+1]) r--; // r 去重
} else if (s < target) l++; else r--;
}
}
}
return res;
}复杂度
时间
O(n³)
i、j 两层各约 n 次，最内层对撞线性
空间
O(1)
排序原地，只用几个指针（不含答案数组）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 四数之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
K 数之和怎么扩展？+
在四数之和外面再套固定层即可：K 数之和 = 固定 K−2 个数 + 最内层两数对撞，时间 O(n^(K−1))。可写成递归通解。
为什么累加要用 long？+
四个 int 相加可能超过 int 范围（约 21 亿）。先转 long 再加，避免溢出成负数导致比较出错。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 四数之和 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。