给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
样例
例1:
输入:[2,7,11,15]
输出:[]
例2:
输入:[-1,0,1,2,-1,-4]
输出:[[-1, 0, 1],[-1, -1, 2]]
注意事项
在三元组(a, b, c)，要求a <= b <= c。
结果不能包含重复的三元组。
暴力解法，时间复杂度O(N^3)，空间复杂度O(1)：
class Solution {
public:
/**
* @param numbers: Give an array numbers of n integer
* @return: Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int>> threeSum(vector<int> &numbers) {
// write your code here
vector<vector<int>> res;
std::sort(numbers.begin(), numbers.end());
size_t n = numbers.size();
int i=0, j,k;
while (i < n-2) {
j = i+1;
while (j < n-1) {
k = j+1;
while (k < n) {
if (numbers[i] + numbers[j] + numbers[k] == 0) {
res.push_back({numbers[i], numbers[j], numbers[k]});
break;
}
k++;
while(k<n && numbers[k]==numbers[k-1]) k++;
}
j++;
while (j<n-1 && numbers[j]==numbers[j-1]) j++;
}
i++;
while (i<n-2 && numbers[i] == numbers[i-1]) i++;
}
return res;
}
};
双指针解法，时间复杂度O(N^2)，空间复杂度O(1)：
class Solution {
public:
/**
* @param numbers: Give an array numbers of n integer
* @return: Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int>> threeSum(vector<int> &numbers) {
// write your code here
vector<vector<int>> res;
std::sort(numbers.begin(), numbers.end());
size_t n = numbers.size();
int i=0, j,k;
while (i < n-2) {
j = i + 1;
k = n - 1;
while (j < k) {
int sum3 = numbers[i] + numbers[j] + numbers[k];
if (sum3 < 0) {
j++;
while (j<k && numbers[j] == numbers[j-1]) j++;
} else if (sum3 > 0) {
k--;
while (j<k && numbers[k] == numbers[k+1]) k--;
} else {
res.push_back({numbers[i], numbers[j], numbers[k]});
// break; // for result can be [[-2,-1,3], [-2,1,1]]
j++;
while (j<k && numbers[j] == numbers[j-1]) j++;
k--;
while (j<k && numbers[k] == numbers[k+1]) k--;
}
}
i++;
while (i<n-2 && numbers[i] == numbers[i-1]) i++;
}
return res;
}
};