My 16ms C++ solution


  • 0
    D
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if (nums.size()<4) return res;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        for (int i = 0;i < n-3;) {
            if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if (nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target) {
                ++i;
                continue;
            }
            for (int j = i+1;j < n-2;) {
                int sum = target-(nums[i]+nums[j]);
                if (nums[j+1]+nums[j+2]>sum) break;
                if (nums[n-2]+nums[n-1]<sum) {
                    ++j;
                    continue;
                }
                int l = j+1,h = n-1;
                while (l < h) {
                    if (nums[l]+nums[h] < sum) ++l;
                    else if (nums[l]+nums[h] > sum) --h;
                    else {
                        vector<int> triplet(4,0);
                        triplet[0] = nums[i];
                        triplet[1] = nums[j];
                        triplet[2] = nums[l];
                        triplet[3] = nums[h];
                        res.push_back(triplet);
                    
                        while (l < h&&nums[l]==triplet[2]) ++l;
                        while (l < h&&nums[h]==triplet[3]) --h;
                    }
                }
                j++;
                while (j < n-2&&nums[j]==nums[j-1]) ++j;
            }
            i++;
            while (i < n-3&&nums[i]==nums[i-1]) ++i;
        }
        return res;
    }

Log in to reply
 

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