1.问题
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
2.说明
输入说明：
首先输入n表示有n个数组；
数组n个数组；
输入target表示四数之和等于target
输出说明：
输出所有四数之和等于target的四元组
3.范例
输入范例：
6
1 0 -1 0 -2 2
0
输出范例：
-1 0 0 1
-2 -1 1 2
-2 0 0 2
4.思路
四数之和和三数之和算法思路一样，也是使用双指针，只是四数之和增加了一个数，因此也增加了一个下标，使用k表示，因此也是增加了一层for循环，同时也是需要对 k 进行去重和剪枝。
5.代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { vector<vector<int>> foursum(vector<int> &nums,int target) { sort(nums.begin(),nums.end()); vector<vector<int>> result; for(int k=0;k<nums.size();k++) { //剪枝 if(nums[k]>target&&nums[k]>=0) break; //对nums[k]去重 if(k>0&&nums[k]==nums[k-1]) continue; for(int i=k+1;i<nums.size();i++) { if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0) break; if(i>0&&nums[i]==nums[i-1]) continue; int left=i+1; int right=nums.size()-1; while(left<right) { if(nums[k]+nums[i]+nums[left]+nums[right]>target) right--; else if(nums[k]+nums[i]+nums[left]+nums[right]<target) left++; else { result.push_back({nums[k],nums[i],nums[left],nums[right]}); //去重逻辑应该放在找到一个三元组之后，对b 和 c去重 while(right>left&&nums[right]==nums[right-1]) right--; while(right>left&&nums[left]==nums[left+1]) left++; //找到答案时，双指针同时收缩 right--; left++; } } } } return result; } }; int mian() { //四数之和 int n; cin>>n; vector<int> nums; int data; for(int i=0;i<n;i++) { cin>>data; nums.push_back(data); } int target; cin>>target; vector<vector<int>> res=Solution().foursum(nums,target); for(int i=0;i<res.size();i++) { for(int j=0;j<4;j++) { cout<<res[i][j]<<" "; } cout<<endl; } return 0; }