3Sum: Finding Triplets That Sum to Zero
3Sum: Finding Triplets That Sum to Zero
The problem: given an array, find all unique triplets that sum to zero.
Core idea
The 3Sum approach works much like 2Sum. Both use the two-pointer technique. The difference is de-duplication. For sorted arrays, removing duplicates means sliding pointers until we hit different elements.
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if (nums.size() < 3) return res;
// Sort first
sort(nums.begin(), nums.end());
for(int i=0;i<nums.size()-2&&nums[i]<=0;++i) {
int start=i+1;
int end=nums.size()-1;
// Two pointers
while(start<end) {
int sum = nums[i]+nums[start]+nums[end];
if (sum<0) ++start;
else if(sum>0) --end;
else {
vector<int> v(3);
v[0]=nums[i];
v[1]=nums[start];
v[2]=nums[end];
res.push_back(v);
// After finding a triplet, slide pointers to skip duplicates
do {
++start;
} while(start<end && nums[start-1]==nums[start]);
do {
--end;
} while(start<end && nums[end+1]==nums[end]);
}
}
// The first number also needs de-duplication
while(i<nums.size()-2 && nums[i+1]==nums[i]) ++i;
}
return res;
}Key insights
Two-pointer sliding for de-duplication. The same 4Sum logic works identically. Pick two numbers first, then use two pointers to find four indices that sum to a target value. Same de-duplication thinking applies.
#two-pointers