Proved to be a best O(n^2), worst O(n^3) solution


  • 0
    H

    with a map to record pairs of indexes with same sum.
    iterator the first 2 number i, j, and find remain in the map, if the first index of the pair if bigger than j, than we found a result.

    when for each 2sum there is only one pair of indexes, the time complexity is O(n^2)

    for a corner case: 1,1,1,1,1,1,1,1
    the map is:

    key vector length

    2 n*(n-1)/2

    how ever there is only one valid i=1,j=1, time complexity is O(n^2)

    for the worst case: 1,2,3,4,5,6,7,8,9
    the map is:

    key vector length

    3 1

    4 1

    5 2

    6 2

    7 3

    8 3

    9 4

    10 4

    11 4

    12 3

    13 3

    14 2

    15 2

    16 1

    17 1

    the average vector length is n/4. therefore time complexity is O(n^3)

    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > res;
        int n=num.size();
        if(n==0)return res;
        sort(num.begin(),num.end());
        unordered_map<int, vector<pair<int,int>> > mp;
        unordered_map<int,vector<pair<int,int>> >::iterator it;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                mp[num[i]+num[j]].push_back(pair<int,int>(i,j));
            }
        }
        
        vector<int> tmp;
        int sum=0;
        for(int i=0;i<n;i++)
        {
    		if(i>0&&num[i]==num[i-1])continue;
            sum+=num[i];
            tmp.push_back(num[i]);
            for(int j=i+1;j<n;j++)
            {
    			if(j>i+1&&num[j]==num[j-1])continue;
                sum+=num[j];
                it=mp.find(target-sum);
                if(it!=mp.end())
                {
    				tmp.push_back(num[j]);
    				int vsize=it->second.size();
    				for(int k=vsize-1;k>=0;k--)
    				{
    					if(it->second[k].first<=j)break;
    					if(k+1<vsize&&num[it->second[k].first]==num[it->second[k+1].first])continue;
    					tmp.push_back(num[it->second[k].first]);
    					tmp.push_back(num[it->second[k].second]);
    					res.push_back(tmp);
    					tmp.pop_back();
    					tmp.pop_back();
    				}
    				tmp.pop_back();
                }
                sum-=num[j];
            }
            tmp.pop_back();
            sum-=num[i];
        }
        return res;
    }
    

    another solution is obviously O(n^3), actually it's faster than the above one(372ms):

     vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > res;
        int n=num.size();
        if(n==0)return res;
        sort(num.begin(),num.end());
        unordered_map<int,int> mp;
        unordered_map<int,int> mp2;
        unordered_map<int,int>::iterator it;
        for(int i=0;i<n;i++)
        {
            mp[num[i]]=i;
            for(int j=i+1;j<n;j++)
            {
                mp2[num[i]+num[j]]=i;
            }
        }
        
        vector<int> tmp;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(i>0&&num[i]==num[i-1])continue;
            sum+=num[i];
            tmp.push_back(num[i]);
            for(int j=i+1;j<n;j++)
            {
                if(j>i+1&&num[j]==num[j-1])continue;
                sum+=num[j];
                it=mp2.find(target-sum);
                if(it!=mp2.end()&&it->second>j)
                {
                    tmp.push_back(num[j]);
                    for(int k=j+1;k<n;k++)
                    {
                        if(k>j+1&&num[k]==num[k-1])continue;
                        sum+=num[k];
                        it=mp.find(target-sum);
                        if(it!=mp.end()&&it->second>k)
                        {
                            tmp.push_back(num[k]);
                            tmp.push_back(it->first);
                            res.push_back(tmp);
                            tmp.pop_back();
                            tmp.pop_back();
                        }
                        sum-=num[k];
                    }
                    tmp.pop_back();
                }
                sum-=num[j];
            }
            tmp.pop_back();
            sum-=num[i];
        }
        return res;
    }

Log in to reply
 

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