# 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());

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;
}
}

}

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) {

// 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--;

}
}
};
``````