My 16ms c++ code


  • 96
    C
    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> total;
            int n = nums.size();
            if(n<4)  return total;
            sort(nums.begin(),nums.end());
            for(int i=0;i<n-3;i++)
            {
                if(i>0&&nums[i]==nums[i-1]) continue;
                if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
                if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
                for(int j=i+1;j<n-2;j++)
                {
                    if(j>i+1&&nums[j]==nums[j-1]) continue;
                    if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                    if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                    int left=j+1,right=n-1;
                    while(left<right){
                        int sum=nums[left]+nums[right]+nums[i]+nums[j];
                        if(sum<target) left++;
                        else if(sum>target) right--;
                        else{
                            total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                            do{left++;}while(nums[left]==nums[left-1]&&left<right);
                            do{right--;}while(nums[right]==nums[right+1]&&left<right);
                        }
                    }
                }
            }
            return total;
        }
    };

  • 0
    S

    cooooooooooooooooooooooooooooool!


  • 9
    X

    Good Idea. The key point is to add checking at the start of the loop.
    At loop 1:

    if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
    if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
    

    At loop 2:

    if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
    if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
    

    Then we skip this loop to avoid a waste of time.


  • 0
    Z

    Key idea is still as others with two pointers. But it uses early pruning as you just pointed out.


  • 4
    V

    if(i>0&&nums[i]==nums[i-1]) continue;
    What it's meaning?
    in this case [-1,-1,-1,0,1,2,3] 0 ,your code sames like will skip [-1,-1,0,2] answer after find [
    -1,-1,-1,3 ].


  • 0
    S

    Great idea!!!!!


  • 0
    C

    This is a very good optimization for general cases, but it doesn't help on worst cases, I think the time complexity of this algorithm is still O(n^3logn) right?


  • 0

    clean implementation!


  • 0

    You cutting edge accelerate the speed is really specific......

      if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
    
      if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
    

    Can accelerate the code from 100ms to 16ms !


  • 0

    You are right it accelerate from 100ms to 16ms ! Pruning is really useful.


  • 2
    M

    smart break and continue statements!


  • 0
    P

    your pruning is excellent!!!!!! reduce 108ms to 16ms


  • 0
    D

    pruning is the king!


  • 1

    Enclosing my KSum yet still best submission here combining portability and performance perfectly in this case.

    class Solution {
    private:
        const int K = 4;
        int size;
        void search(const vector<int>& nums, int pos, int k, int target, vector<int>& v, vector<vector<int>>& vv)
        {
            if(k == 2)
            {
                int l = pos, r = size-1;
                while(l < r)
                {
                    int t = nums[l]+nums[r];
                    if(t > target) r--;
                    else if(t < target) l++;
                    else
                    {
                        v.push_back(nums[l++]);
                        v.push_back(nums[r--]);
                        vv.push_back(v);
                        v.pop_back(), v.pop_back();
                        while(l<r && nums[l]==nums[l-1]) l++;
                        while(l<r && nums[r]==nums[r+1]) r--;
                    }
                }
            }
            else
            {
                for(int j = pos; j <= size-k; ++j)
                {
                    int sum = 0;
                    for(int i = j; i < k+j; ++i) sum += nums[i];
                    if(sum > target) break;
                    sum = nums[j];
                    for(int i = 0; i < k-1; ++i) sum += nums[size-1-i];
                    if(sum < target) continue;
                    v.push_back(nums[j]);
                    search(nums, j+1, k-1, target-nums[j], v, vv);
                    v.pop_back();
                    while(j<=size-k && nums[j+1]==nums[j]) j++;
                }
            }
        }
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) 
        {
            sort(nums.begin(), nums.end());
            size = nums.size();
            vector<int> v;
            vector<vector<int>> vv;
            search(nums, 0, K, target, v, vv);
            return vv;
        }
    };
    

  • 0
    P

    why I use

    total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});

    Run Code Status diaplayed :Memory Limit Exceeded


  • 0

    @pointless Show your code first.


  • 0
    P

    @LHearen

    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums,int target) {
            vector<vector<int>>s;
            while(nums.size()<=3)return s;
            int n=nums.size();
            sort(nums.begin(),nums.end());
            //int init=nums[0]+nums[1]+nums[2]+nums[3];
            //if(init>target)return s;
            //else if(init==target)s.push_back(vector<int>{nums[0],nums[1],nums[2],nums[3]});
    
            for(int i=0;i<n-3;i++){
                if(i>0&&nums[i]==nums[i-1]) continue;
                if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
                if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
                for(int j=i+1;j<n-2;j++){
                    if(j>i+1&&nums[j]==nums[j-1]) continue;
                    if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                    if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                    int k=j+1;
                    int l=n-1;
                    while(k<l){
                        int sum=nums[i]+nums[k]+nums[l]+nums[j];
                        if(sum==target){
                            //vector<int>tmp(4,0);
                            //tmp[0]=nums[i];
                            //tmp[1]=nums[j];
                            //tmp[2]=nums[k];
                            //tmp[3]=nums[l];
                            //s.push_back(tmp);
                            s.push_back(vector<int>{nums[i],nums[j],nums[k],nums[l]});
                            //while(k<l&&nums[k]==tmp[2])k++;
                            //while(k<l&&nums[l]==tmp[3])l--;
                            while(k<l&&nums[k]==nums[k-1])k++;
                            while(k<l&&nums[l]==nums[l-1])l--;
                            //continue;
                        }
                        else (sum>target)?l--:k++;
                        }
                    }
                    
                }
    
            //}
            return s;
        }
        
    };
    

  • 0

    @pointless Your code is fixed now, be careful next time. Good luck.

    if(sum==target)
    {
        s.push_back(vector<int>{nums[i],nums[j],nums[k++],nums[l--]});
        while(k<l&&nums[k]==nums[k-1])k++;
        while(k<l&&nums[l]==nums[l+1])l--;
    }
    

  • 0
    P

    @LHearen oh,I see.
    Thanks.


  • 0

    Awesome!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


Log in to reply
 

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