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:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- 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)
解题思路o(n2)：
先对数组进行排序，排序后以每一个数组元素为目标值，在其他的元素中寻找余下的两个元素，使这三个元素之和为0；那么此题就转化为leetcode中另一道TwoSum的问题，由于3Sum已经提前排序，因此TwoSum中的hash表技巧在这种思路下就没有时间复杂度优势了。
注意：
1、不需要遍历所有数组元素，只需要将所有非正元素，或者所有非负元素依次作为目标值即可；
2、在相同目标值的前提下，TwoSum可能有多种匹配对（当然）；
3、此题最重要的是避免返回的答案序列出现重复，重复有两种情况：
（1）TwoSum的计算结果出现重复。
解决方法：以i和j从序列两头向中间遍历，如果遇到符合条件的i和j，则跨越所有值相同的i和j，再继续遍历之后的数字；
（2）目标值出现重复。
解决方法：a. 从左向右遍历，只遍历非正数；（或者从右向左遍历，只遍历非负数）
b. 跨过所有相同的重复数字；
重复去除的关键在于，第一次出现重复数字时，其数字选择完全包含了之后重复数字的选择，那么之后遇到重复数字直接略过就行了。
解题步骤：
1、复制输入数组，并对复制数组进行排序；
2、新建一个保存结果的二维数组；
3、从0开始遍历，直到复制数组元素<=0：
（1）将遍历到的元素下标，随同复制数组以及保存结果的二维数组，传入FindTwoSum函数中。
（2）略过和遍历到的元素相同的元素；
4、返回结果数组；
对于FindTwoSum：
1、从遍历元素下标+1，到数组末尾，两端向中间遍历此数组：
（1）判断两端及遍历元素，三者之和是否为0；进而做++i和++j的处理；
（2）三者和为0，则这三者放入结果数组中，并且略过重读的num[++i]和num[--j]；
AC代码：
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
sort(num.begin(), num.end());
int size = num.size();
vector<vector<int> > result;
for (int i = ; i < size - && num[i] <= ; ++i) {
FindTwoSum(result, num, i);
while (num[i] == num[i+])
++i;
}
return result;
}
void FindTwoSum(vector<vector<int> > &result, vector<int> num, int target_idx) {
int target = num[target_idx];
int i = target_idx + ;
int j = num.size() - ;
while (i < j) {
if (num[i] + num[j] + target > ) {
--j;
} else if (num[i] + num[j] + target < ) {
++i;
} else {
vector<int> oneMatch {target, num[i], num[j]};
result.push_back(oneMatch);
while (num[i] == num[++i]);
while (num[j] == num[--j]);
}
}
return;
}
};