给出一个有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。

vector<vector<int> > threeSum(vector<int> &nums) 
{
vector<vector<int>> res;
//为啥要sort呢，因为要用到双指针来遍历找两数之和，只有在从小到大排序之后的结果上，才能根据判断移动start和end
sort(nums.begin(), nums.end()); for (int k = 0; k < nums.size() - 2; ++k) {if (nums[k] > 0) break;//处理数组中有相同数的情况if (k > 0 && nums[k] == nums[k - 1]) continue;//求解两个数相加等于某个数，用双指针法!!!int target = 0 - nums[k], i = k + 1, j = nums.size() - 1;while (i < j) {if (nums[i] + nums[j] == target) {res.push_back({nums[k], nums[i], nums[j]});//处理数组中有相同数的情况 ，注意，这里内部嵌套的是while语句while (i < j && nums[i] == nums[i + 1]) ++i;while (i < j && nums[j] == nums[j - 1]) --j;++i; --j;} // 因为是排序好了的，所以如果 nums[i]+nums[j]<target ，则向右移,反之向左移动else if (nums[i] + nums[j] < target) ++i;else --j;}}
return res;
}