# A little trick thing could reduce the worst caes.

• for duplicates ,it will have at most 4 same number .so if we reduce the numbers first ,
the worst case of this algorithm will be n^2logn.
i saw some one just remain all the same pairs ,but in worst case ,it will become n^4,which is all them are the same number.

``````struct Pair2{
int a,b;
int ai,bi;
int sum()const{
return a+b;
}
bool operator< (const Pair2&p) const{
return sum()<p.sum();
}
bool overlap(Pair2& p)
{
return ai==p.ai||bi==p.ai||ai==p.bi||bi==p.bi;
}
};
struct Pair4{
int a,b,c,d;
Pair4(Pair2& p1,Pair2&p2){
int k[4]={p1.a,p1.b,p2.a,p2.b};
sort(k,k+4);
a=k[0];
b=k[1];
c=k[2];
d=k[3];

}
vector<int> toV4(){
vector<int> v;
v.push_back(a);
v.push_back(b);
v.push_back(c);
v.push_back(d);
return v;
}
};

struct hash_stru{
size_t operator ()(const Pair4& p)const {
return p.a*p.b*p.c*p.d+p.a+p.b+p.c+p.d;
}
};
struct same_stru{
bool operator()(const Pair4 &p1,const Pair4 &p2) const
{
return p1.a==p2.a&&p1.b==p2.b&&p1.c==p2.c&&p1.d==p2.d;
}
};
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
int cnt=0;
sort(num.begin(),num.end());
vector<int> num2;
//at most four of them can be the same.
for(int i=0;i<num.size();i++)
{
if(i==0||num[i]!=num[i-1]){
cnt=1;
}
else if(num[i]==num[i-1])
{
cnt++;
if(cnt>4)
}
num2.push_back(num[i]);
}
vector<Pair2> vP;
for(int i=0;i<num2.size();i++)
for(int j=i+1;j<num2.size();j++)
{
Pair2 p;
p.a=num2[i];p.ai=i;
p.b=num2[j];p.bi=j;
vP.push_back(p);
}
sort(vP.begin(),vP.end()); //O(n^2logn)
int i=0;
int j=vP.size()-1;
vector<Pair4> vp4;
while(i<j){
if(vP[i].sum()+vP[j].sum()<target)
i++;
else if(vP[i].sum()+vP[j].sum()>target)
j--;
else
{
//for all A[i] & A[j] to be the same
int ci=i,cj=j;
while(ci<j&&vP[ci].sum()==vP[i].sum())
ci++;
while(cj>i&&vP[cj].sum()==vP[j].sum())
cj--;
if(ci>=cj){ //A[i...j] is the same.

}
for(int ii=i;ii<ci;ii++)
{
for(int jj=max(i+1,cj+1);jj<=j;jj++)
{
if(!vP[ii].overlap(vP[jj]))
{
vp4.push_back(Pair4(vP[ii],vP[jj]));
}
}
}
//after all ,
i=ci;
j=cj;
}
}
//remove the same
unordered_set<Pair4,hash_stru,same_stru> st;
vector<vector<int> > ret;
for(int i=0;i<vp4.size();i++)//O(n^2)
{
if(st.find(vp4[i])==st.end())
{
st.insert(vp4[i]);
ret.push_back(vp4[i].toV4());
}
}
return ret;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.