题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、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
解题思路
同2数，3数之和一样。固定一个，移动另一个。
4数之和那就是，固定2个，然后用双指针遍历其他的。
注意对每个数都需要进行去重操作。
代码
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); vector<vector<int>> ret; int n= nums.size(); for(int a=0;a<n;a++) { for(int b=a+1;b<n;b++) { int c=b+1,d=n-1; while(c<d) { //越界处理 long long sum=(long long)nums[a]+nums[b]+nums[c]+nums[d]; if(sum>target) d--; else if(sum<target) c++; else { ret.push_back({nums[a],nums[b],nums[c],nums[d]}); //c、d去重 while(c+1<n&&nums[c]==nums[c+1]) c++; while(d-1>=0&&nums[d]==nums[d-1]) d--; //下一个 c++;d--; } } //b去重 while(b+1<n&&nums[b]==nums[b+1]) b++; } //a去重 while(a+1<n&&nums[a]==nums[a+1]) a++; } return ret; } };
