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中另一道的问题，由于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代码：

1 class Solution { 2 public: 3     vector
     
      
        > threeSum(vector
       
         &num) { 4         sort(num.begin(), num.end()); 5         int size = num.size(); 6         vector
        
         
           > result; 7  8         for (int i = 0; i < size - 2 && num[i] <= 0; ++i) { 9             FindTwoSum(result, num, i);10             while (num[i] == num[i+1])11                 ++i;12         }13         return result;14     }15     16     void FindTwoSum(vector
          
           
             > &result, vector
            
              num, int target_idx) {17 int target = num[target_idx];18 int i = target_idx + 1;19 int j = num.size() - 1;20 while (i < j) {21 if (num[i] + num[j] + target > 0) {22 --j;23 } else if (num[i] + num[j] + target < 0) {24 ++i;25 } else {26 vector
             
               oneMatch {target, num[i], num[j]};27 result.push_back(oneMatch);28 while (num[i] == num[++i]);29 while (num[j] == num[--j]);30 }31 }32 return;33 }34 };