英文原文
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
中文题目
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
通过代码
高赞题解
思路：
四数之和与前面三数之和的思路几乎是一样的，嗝。（刚好前些天才写了三数之和的题解）
如果前面的三数之和会做了的话，这里其实就是在前面的基础上多添加一个遍历的指针而已。
会做三数之和的可以不用看下面的了。。
使用四个指针(a<b<c<d)。固定最小的a和b在左边，c=b+1,d=_size-1 移动两个指针包夹求解。
保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移，偏小时c右移。c和d相
遇时，表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环，当b循环结束后。
a++，进入下一轮a循环。 即(a在最外层循环，里面嵌套b循环，再嵌套双指针c,d包夹求解)。
准备工作：
因为要使用双指针的方法，排序是必须要做der~。 时间复杂度O(NlogN).
解决重复解：
上面的解法存在重复解的原因是因为移动指针时可能出现重复数字的情况。所以我们要确保移动指针后，
对应的数字要发生改变才行哦。
时间复杂度：
a遍历O(N)里嵌套b遍历O(N)再嵌套c,d双指针O(N)--> O(N^3)。 总比暴力法O(N^4)好些吧。
.png)
代码块
class Solution{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<vector<int> > res;
if(nums.size()<4)
return res;
int a,b,c,d,_size=nums.size();
for(a=0;a<=_size-4;a++){
if(a>0&&nums[a]==nums[a-1]) continue; //确保nums[a] 改变了
for(b=a+1;b<=_size-3;b++){
if(b>a+1&&nums[b]==nums[b-1])continue; //确保nums[b] 改变了
c=b+1,d=_size-1;
while(c<d){
if(nums[a]+nums[b]-target<-(nums[c]+nums[d]))//原写法num[a]+num[b]+num[c]+num[d]<target为了防止溢出，见下面的补充修改
c++;
else if(nums[a]+nums[b]-target>-(nums[c]+nums[d]))//同上
d--;
else{
res.push_back({nums[a],nums[b],nums[c],nums[d]});
while(c<d&&nums[c+1]==nums[c]) //确保nums[c] 改变了
c++;
while(c<d&&nums[d-1]==nums[d]) //确保nums[d] 改变了
d--;
c++;
d--;
}
}
}
}
return res;
}
};
2021.9.6补充修改：
因为官方增加了一个新的用例
{1000000000，1000000000，1000000000，1000000000} 0
导致了代码出现溢出错误，是因为int的只能到表示[-2147483648,2147483647]，所以在判断
num[a]+num[b]+num[c]+num[d]<target
时会溢出。因为不想对代码进行大改了所以将表达式调整为
nums[a]+nums[b]-target<-(nums[c]+nums[d])
这样子就不会溢出了。当然也可以使用long long int来表示数值，这样也不会溢出。(边界处理很重要，但学习
双指针的思想更重要~)
ps:
这份代码现在来看的已经不算高效了TAT，如果想要学习回溯剪枝等各种优化的话可以去参考其他人的文
章。。这里妮，只是想要提供一个非常朴素简单直接的逻辑，希望可以让初学的伙伴门能够快速理解双指
针算法的核心，所以不会再作其他效率优化就是说。。。大家也别嫌弃它效率差了拜托拜托😥。。。
觉得有用给点个赞呢，看到右上角小铃铛提示有人点赞的感觉简直不要太爽。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 240183 | 608141 | 39.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 两数之和 | 简单 |
| 三数之和 | 中等 |
| 四数相加 II | 中等 |
