给定一个包含 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]
]来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
分析：
跟三数之和的做法是一样的
假设满足要求的数k1<=k2<=k3<=k4
先排序，然后固定k1和k2，通过二分寻找k3和k4
复杂度：O(N*N*log N)
class Solution {
public:
vector<vector<int> > fourSum(vector<int>& a, int t)
{
vector<vector<int> >vv;
vector<int> v;
set<vector<int> > s;
set<vector<int> >::iterator it;
int n=a.size();
if(n<4)
return vv;
sort(a.begin(),a.end());
for(int i=0; i<n-3; i++)
{
for(int j=i+1; j<n-2; j++)
{
int l=j+1;
int h=n-1;
while(l<h)
{
int sum=a[i]+a[j]+a[l]+a[h];
if(sum==t)
{
v.clear();
v.push_back(a[i]);
v.push_back(a[j]);
v.push_back(a[l]);
v.push_back(a[h]);
s.insert(v);
l++;
h--;
}
else if(sum<t)
{
l++;
}
else if(sum>t)
{
h--;
}
}
}
}
if(s.size()!=0)
{
for(it=s.begin(); it!=s.end(); it++)
{
vv.push_back(*it);
}
}
return vv;
}
};