# 15 - 3Sum

## 解法一 - Two Pointer

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> triplets;
int n = nums.size();

sort(nums.begin(), nums.end());

// Note:
// 1. Iterate to n-2 only
// 2. Need to skip same element to avoid duplicate triplets
for(int i=0; i<n-2; i++) {
// skip same element to avoid duplicate triplets
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
searchPair(nums, -nums[i], i+1, triplets);
}

return triplets;
}

private:
void searchPair(vector<int>& nums, int target, int start, vector<vector<int>>& triplets) {
int l=start, r=nums.size()-1;

while(l<r) {
if(nums[l]+nums[r] == target) {
triplets.push_back({-target, 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--;

while (l < r && nums[l] == nums[l-1]) {
l++;  // skip same element to avoid duplicate triplets
}
while (l < r && nums[r] == nums[r+1]) {
r--;  // skip same element to avoid duplicate triplets
}
}
else if(nums[l]+nums[r] > target) r--;
else if(nums[l]+nums[r] < target) l++;
}
}
};
``````