A little trick thing could reduce the worst caes.


  • 1
    N

    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++)
        	{
        		bool add=true;
        		if(i==0||num[i]!=num[i-1]){
        			cnt=1;
        			add=true;
        		}
        		else if(num[i]==num[i-1])
        		{
        			cnt++;
        			if(cnt>4)
        				add=false;
        		}
        		if(add)
        			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;
        }
        };

Log in to reply
 

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