A c++ O(n^2logn) solution


  • -1
    E

    class Solution {
    public:
    struct position
    {
    int sum,l,r;
    position(){}
    position(int _sum,int _l,int _r): sum(_sum),l(_l),r(_r) {}
    bool operator <(const position &a) const
    {
    return (sum<a.sum)||(sum==a.sum&&l<a.l);
    }
    };
    vector<position> pos;
    map<string,int> mp;

    string tostring(int num)
    {
        string s="";
        while(num)
        {
            char c=num%10+'0';
            s=s+c;
            num/=10;
        }
        return s;
    }
    
    int can(int i,int j,int l,int r)
    {
        return (i!=l)&&(i!=r)&&(j!=l)&&(j!=r);
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<int> twosum;
        twosum.clear();
        pos.clear();
        mp.clear();
        vector<vector<int> > ret;
        ret.clear();
        int sz=nums.size();
        for(int i=0;i<sz;i++)
        {
            for(int j=i+1;j<sz;j++)
            {
                pos.push_back(position(nums[i]+nums[j],i,j));
                twosum.push_back(nums[i]+nums[j]);
            }
        }
        sort(pos.begin(),pos.end());
        sort(twosum.begin(),twosum.end());
        int i=0,j=i+1;
        for(i=0;i<sz;i++)
        {
            for(j=i+1;j<sz;j++)
            {
                int curtwo=nums[i]+nums[j];
                int curtwopos=(2*sz-j-2)*(j+1)/2;
                int findpos=lower_bound(twosum.begin(),twosum.end(),target-curtwo)-twosum.begin();
                while(findpos<twosum.size()&&twosum[findpos]==target-curtwo)
                {
                    vector<int> newans;
                    newans.clear();
                    int l=pos[findpos].l,r=pos[findpos].r;
                    int n1,n2,n3,n4;
                    n1=nums[i],n2=nums[j],n3=nums[l],n4=nums[r];
                    newans.push_back(n1),newans.push_back(n2),newans.push_back(n3),newans.push_back(n4);
                    sort(newans.begin(),newans.end());
                    string s="";
                    s=tostring(newans[0])+","+tostring(newans[1])+","+tostring(newans[2])+","+tostring(newans[3]);
                    if(can(i,j,l,r)&&mp[s]==0)
                    {
                        mp[s]=1;
                        ret.push_back(newans);
                    }
                    findpos++;
                }
            }
            while(i+1<sz&&nums[i+1]==nums[i]) i++;
        }
        return ret;
    }
    

    };


Log in to reply
 

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