# 18 - 4Sum

解法一 - Two Pointer

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n=nums.size();
        sort(nums.begin(), nums.end());

        vector<vector<int>> quadruplets;
        for(int i=0; i<n-3; i++) {
            if(i>0 && nums[i-1] == nums[i]) continue;

            for(int j=i+1; j<n-2; j++) {
                if(j>i+1 && nums[j-1] == nums[j]) continue;
                searchPair(nums, target, i, j, quadruplets);
            }
        }

        return quadruplets;
    }

private:
    void searchPair(vector<int>& nums, int target, int first, int second, vector<vector<int>>& quadruplets) {
        int l=second+1, r=nums.size()-1;

        while(l<r) {
            int sum = nums[first] + nums[second] + nums[l] + nums[r];

            if(sum == target) {
                quadruplets.push_back({nums[first], nums[second], nums[l], nums[r]});

                // Intuitively, we should only do l++ or r--
                // so that we won't miss the case of nums[l]+nums[r-1] or nums[l+1]+nums[r]
                // But think deeper, if we only do r--
                // After preventing duplicates, we know that
                // nums[l] and nums[new r] cannot fulfill sum==target
                // So we won't miss anything even we do l++ and r--
                l++;
                r--;

                // Need to prevent duplicates
                while(l<r && nums[l] == nums[l-1]) l++;
                while(r>l && nums[r] == nums[r+1]) r--;
            }
            else if(sum < target) l++;
            else r--;

        }
    }
};