Description
https://oj.leetcode.com/problems/3sum/
Difficulty: 3.0/5.0
Solution
3Sum is an extension to 2Sum. We are required to get all non-redundant triplets whose sum is zero. In this case, we enumerate each unqiue left elemenet in a triplet and use the 2Sum algorithm to find the mid and right element. Note that we can also enumerate each unique right element, but enumerating the middle one would be painful.
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > result;
sort(num.begin(), num.end());
int left = 0;
while(left < ((int)num.size()-2)){
int mid = left+1, right = num.size() -1;
while(mid < right){
if (num[left] + num[right] + num[mid] == 0){
vector<int>tp;
tp.push_back(num[left]);
tp.push_back(num[mid]);
tp.push_back(num[right]);
result.push_back(tp);
do { right --;} while(right > mid && num[right] == num[right+1]);
do { mid ++; } while(right > mid && num[mid] == num[mid-1]);
}
else if (num[left] + num[right] + num[mid] > 0)
do { right --;} while(right > mid && num[right] == num[right+1]);
else
do { mid ++;} while(right > mid && num[mid] == num[mid-1]);
}
do{left ++;}while(left < (int)(num.size()-2) && num[left] == num[left-1]);
}
return result;
}
};4Sum is an simple extension to 3Sum, with another layer of while loop.
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
sort(num.begin(), num.end());
vector<vector<int> > result;
if (num.size() < 4) return result;
int first = 0;
while(first < num.size()-3){
int second = first + 1;
while(second < num.size()-2){
int third = second + 1;
int forth = num.size()-1;
while(third < forth){
int sum = num[first] + num[second] + num[third] + num[forth];
if ( sum == target){
vector<int>tp;
tp.push_back(num[first]);
tp.push_back(num[second]);
tp.push_back(num[third]);
tp.push_back(num[forth]);
result.push_back(tp);
do {forth --;} while(third < forth && num[forth] == num[forth+1]);
do {third ++;} while(third < forth && num[third] == num[third-1]);
}
else if (sum > target)
do {forth --;} while(third < forth && num[forth] == num[forth+1]);
else
do {third ++;} while(third < forth && num[third] == num[third-1]);
}
do {second ++;} while(second < num.size()-2 && num[second] == num[second-1]);
}
do {first ++;} while(first < num.size()-3 && num[first] == num[first-1]);
}
return result;
}
};