O(n^2log n) time and O(n^2) space


  • 0
    N
    public:
        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
            vector<int> E;
            vector<int> F;
            /*for(int i=0;i<A.size();i++)
            cout<<A[i]<<" "<<B[i]<<" "<<C[i]<<" "<<D[i]<<endl;*/
            for(int i=0;i<A.size();i++)
            {
                for(int j=0;j<A.size();j++)
                {
                    E.push_back(A[i]+B[j]);
                }
            }
    //cout<<" here "<<endl;
    
            for(int i=0;i<A.size();i++)
            {
                for(int j=0;j<A.size();j++)
                {
                    F.push_back(C[i]+D[j]);
                }
            }
            int count=0;
            sort(E.begin(),E.end());
            sort(F.begin(),F.end());
            int lans , rans;
            int mid;
    
    //cout<<" here 2"<<endl;
    
            for(int i=0;i<E.size();i++)
            {
    //cout<<"In the e "<<i<<endl;
                lans=rans=-1;
                int lb=0, rb=F.size()-1;// two boundries
                while(lb<=rb)
                {
                    mid=lb+(rb-lb)/2;
                    if( F[mid] == -E[i]&&(mid==0||F[mid-1]<-E[i]))
                    {
                        lans=mid;
                        break;
                    }
                    else if( F[mid] < -E[i] )
                        lb=mid+1;
                    else
                    {
                        rb=mid-1;
                    }
      //              cout<<mid<<" ";
    
                }
                if(lans==-1)    continue;
                lb=lans;
                rb=F.size()-1;
                while(lb<=rb)
                {
                    //cout<<mid<<endl;
                    mid=lb+(rb-lb)/2;
                    if( F[mid] == -E[i]&&(mid+1==F.size() || F[mid+1]> -E[i]))
                    {
                        rans=mid;
                        break;
                    }
                    else if( F[mid] > -E[i] )
                        rb=mid-1;
                    else
                    {
                        lb=mid+1;
                    }
    
                }
                count+=(-lans + rans + 1);
            }
            return count;
    
        }
    };```

Log in to reply
 

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