题目描述：给定一个有n个整数的数组S，找到其中所有由三个数a、b、c组成，使得a + b + c = 0的三元组。如：
given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1], [-1, -1, 2]
]
分析：3个数的和为定值，三重循环肯定可以解决，但复杂度太高。可以先排序，然后在一遍遍历中两边夹。时间复杂度O(n^2)，空间O(1)。这个思路可推广到k-sum，都是先排序，然后 k - 2 层循环，最里面再加层左右夹逼的循环，复杂度O( max{nlgn, n^(k - 1)} )。
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& num) {
vector<vector<int> > v; //解不止一个，要记录所有的三元组
if(num.size() == 0)
return v;
sort(num.begin(), num.end());
for(int i = 0; i < num.size() - 2 && num[i] <= 0; i ++ ) //因为目标值是0，所以每个三元组至少有一个负数，故只用遍历负数即可
{
if(i > 0 && num[i] == num[i - 1]) // 跳过重复元素
continue;
int l = i + 1, r = num.size() - 1; //保证三个数不是同一个数的的前提下的查找最大范围
while(l < r)
{
if(num[l] + num[r] == 0 - num[i])
{
v.push_back({num[i], num[l], num[r]});
//每次找到后分别略过左右两边的重复元素
while(++ l < r && num[l] == num[l - 1]); // 跳过重复元素
while(l < -- r && num[r] == num[r + 1]); // 跳过重复元素
}
else if(num[l] + num[r] > 0 - num[i]) //两数和偏大，右指针往小移
-- r;
else //两数和偏小，左指针往大移
++ l;
}
}
return v;
}
};
