題目描述：給定一個有n個整數(shù)的數(shù)組S憾赁，找到其中所有由三個數(shù)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個數(shù)的和為定值剃法，三重循環(huán)肯定可以解決碎捺，但復(fù)雜度太高〈蓿可以先排序收厨，然后在一遍遍歷中兩邊夾。時間復(fù)雜度O(n^2)优构，空間O(1)诵叁。這個思路可推廣到k-sum，都是先排序钦椭，然后 k - 2 層循環(huán)拧额，最里面再加層左右夾逼的循環(huán)，復(fù)雜度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，所以每個三元組至少有一個負數(shù)德挣，故只用遍歷負數(shù)即可
{
if(i > 0 && num[i] == num[i - 1]) // 跳過重復(fù)元素
continue;
int l = i + 1, r = num.size() - 1; //保證三個數(shù)不是同一個數(shù)的的前提下的查找最大范圍
while(l < r)
{
if(num[l] + num[r] == 0 - num[i])
{
v.push_back({num[i], num[l], num[r]});
//每次找到后分別略過左右兩邊的重復(fù)元素
while(++ l < r && num[l] == num[l - 1]); // 跳過重復(fù)元素
while(l < -- r && num[r] == num[r + 1]); // 跳過重復(fù)元素
}
else if(num[l] + num[r] > 0 - num[i]) //兩數(shù)和偏大恭垦，右指針往小移
-- r;
else //兩數(shù)和偏小，左指針往大移
++ l;
}
}
return v;
}
};
