Question
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Solution
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int> > threeSum(vector<int>& nums) {
// sort nums firstly
sort(nums.begin(), nums.end(), less<int>());
// prepare result
vector<vector<int> > result;
// three iterators
vector<int>::iterator it0, it1, it2;
for (it0 = nums.begin(); it0 < nums.end(); it0++) {
int expect = -(*it0);
if (it0 > nums.begin() && *it0 == *(it0 - 1)) {
continue; // skip same nums
}
it1 = it0 + 1;
it2 = nums.end() - 1;
while (it1 < it2) {
if (*it1 + *it2 < expect) {
it1++;
// skip
while (*it1 == *(it1 - 1) && it1 < it2) {
it1++;
}
} else if (*it1 + *it2 > expect) {
it2--;
// skip
while (*it2 == *(it2 + 1) && it1 < it2) {
it2--;
}
} else {
// equal to expect
vector<int> triplet;
triplet.push_back(*it0);
triplet.push_back(*it1);
triplet.push_back(*it2);
result.push_back(triplet);
it1++;
it2--;
// skip
while (*it1 == *(it1 - 1) && it1 < it2) {
it1++;
}
while (*it2 == *(it2 + 1) && it1 < it2) {
it2--;
}
}
}
}
return result;
}
};
Test Cases
Solution sol;
TEST(Main, Case1) {
vector<int> vec;
// [-1, 0, 1, 2, -1, -4]
vec.push_back(-1);
vec.push_back(0);
vec.push_back(1);
vec.push_back(2);
vec.push_back(-1);
vec.push_back(-4);
vector<vector<int> > r = sol.threeSum(vec);
// [-1, 0, 1]
// [-1, -1, 2]
EXPECT_EQ(r.size(), 2);
EXPECT_EQ(r[0][0], -1);
EXPECT_EQ(r[0][1], -1);
EXPECT_EQ(r[0][2], 2);
EXPECT_EQ(r[1][0], -1);
EXPECT_EQ(r[1][1], 0);
EXPECT_EQ(r[1][2], 1);
}