4sum
4sum，之前2sum 3sum用这个都完成了，但是现在TLE了，时间复杂度O(n^3 logn)
对重复的情况处理就是如果4次循环每一次如果前后都相同的话，一定会重复，因为当前这一个数选了重复的，后面会找到同样的数，但是似乎有点问题，之前还没想到，1 1 2.。。i指向第一个1，j指向第二个1，
如果接下来i指向第二个1，那么j往后指似乎不会和前面重复，似乎算法还有问题，不太确定。
vector<vector<int> > fourSum(vector<int> &num, int target)
{
//int sum=0;
vector<vector<int> >allsolution;
if(num.size()<=3) return allsolution;
sort(num.begin(),num.end());
for(int i=0;i<=num.size()-1;i++)
{
if(i>=1 && num[i]==num[i-1]) continue;
for(int j=i+1;j<=num.size()-1;j++)
{
if(j>=i+2 && num[j]==num[j-1]) continue;
for(int k=j+1;k<=num.size()-1;k++)
{
if(k>=j+2 && num[k] == num[k-1]) continue;
//binarysearch
int low=k+1,high=num.size()-1,x=target-num[i]-num[j]-num[k];
while(low<=high)
{
int mid=(low+high)/2;
if(num[mid]==x)
{
vector<int> onesolution;
onesolution.push_back(num[i]);
onesolution.push_back(num[j]);
onesolution.push_back(num[k]);
onesolution.push_back(num[mid]);
allsolution.push_back(onesolution);
break;
}
else if(num[mid]<x)
low=mid+1;
else
high=mid-1;
}
/*
bool found=binary_search(num+k,num+num.size()-1,sum-a[i]=a[j]=a[k]);
if(found==true)
return
for(int l=k+1;l<=num.size()-1;l++)
{
if(l>=k+2 && num[l]==num[l-1]) continue;
if(num[i]+num[j]+num[k]+num[l]>target) break;
if(num[i]+num[j]+num[k]+num[l]==target)
{
vector<int> onesolution;
onesolution.push_back(num[i]);
onesolution.push_back(num[j]);
onesolution.push_back(num[k]);
onesolution.push_back(num[l]);
allsolution.push_back(onesolution);
}
}*/
}
}
}
return allsolution;
}