My concise C++ Solution Based On 3Sum


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

Log in to reply
 

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