28ms with binary search


  • 0

    Time complexity O(N^3log(N)) for the fourSum, and O(N^2log(N)) for the threeSum with the same strategy.
    Is anyone can obtain the time ~ O(N)-like with the cost of increasing space complexity?

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n=nums.size(); vector<vector<int> > ans;
        if(n<4) return ans;
        sort(nums.begin(), nums.end());
        
        int w, x, y, z, ly, ry, a, b, c, d, dc;
        for(w=0; w<n-3; w++){
            a=nums[w];
            if(a+nums[w+1]+nums[w+2]+nums[w+3]>target) return ans;
            for(x=w+1; x<n-2; x++){
                b=nums[x];
                if(a+b+nums[x+1]+nums[x+2]>target) break;
                for(z=n-1; z>x+1; z--){
                    d=nums[z]; ly=x; ry=z; dc=target-a-b-d; y=(ly+ry)/2;c=nums[y];
                    if(a+b+nums[z-1]+nums[z]<target) break;
                    while(ly!=y && ry!=y){
                        if(c<dc) ly=y;
                        else if(c>dc) ry=y;
                        else if(c==dc){ ans.push_back(vector<int> {a, b, c, d}); break;}
                        y=(ly+ry)/2;c=nums[y];
                        }
                        while(nums[z]==nums[z-1]) {z--; if(z<3) break;}
                    }
                    while(nums[x]==nums[x+1]){x++; if(x>n-3) break;}
                }
                while(nums[w]==nums[w+1]){w++; if(w>n-4) break;}
            }
        return ans;
    }

Log in to reply
 

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