Easy-understand about 4sum


  • 0
    S

    class Solution{

    public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size=nums.size();
        sort(nums.begin(),nums.end());
        int i,j,left,right;    //四个指针
        vector<vector<int>> foursum;
        for(i=0; i < size -3 ;i++)
        {
            if(i>0 && nums[i] ==nums[i-1]) continue;
            for(j=i+1 ;j<size-2 ;j++)
            {
                if(j>i+1 && nums[j] == nums[j-1] ) continue; 
                left=j+1;right=size-1;
                while(left<right)
                {
                    int sum=nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum ==target)
                    {
                        foursum.push_back({nums[i],nums[j],nums[left],nums[right]});
                        do{ left++ ; } while(left<right && nums[left-1] == nums[left]);   // eliminate duplicate quadruplets
                        do{ right--; } while(left<right && nums[right+1]==nums[right]);
                    }
                    else if(sum<target)
                        left++;
                    else
                        right--;
                }
            }
        }
        return foursum;
    }
    

    };}


Log in to reply
 

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