题面

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

给定数组，找出其中不重复的三个和为0的元素集合。

样例

1. Given array nums = [-1, 0, 1, 2, -1, -4],
solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
2. Given array nums = [0， 0， 0],
solution set is:
[
  [0, 0, 0]
]
note: this example may cause something wrong!
(heap overflow? Need you to try it.)

思路

按照我以往的傻瓜思路，暴力来解决的话，time complexity will be O(n3)，that's fool.

这里参考了（抄）一个简单易于理解的solution 👉  C++ two-pointes solution

1. 不可避免地要遍历数组；

2. 固定一个元素i，通过两点法去[i+1, size()-1]中搜索另外两个数字；两点法在那个“盛最多的水”中已经见过了。

3. 若找到，就将三数集合vector<int> {i, l, r}压入结果集vector<vector<int>> res中; 

(二维vector，怎么压入一行元素呢？ res.push_back(vector<int> {...}) )

Note : 怎么才能避免出现重复呢？

处理前，先对数组进行排序，而后在处理过程中，遇到相同的i, l, r 跳过即可。

源码

 1 class Solution {
 2 public:
 3     vector<vector<int>> threeSum(vector<int>& nums) {
 4         vector<vector<int>> res;
 5         sort(nums.begin(), nums.end());
 6         for(int i=0; i<nums.size(); i++)
 7         {
 8             if(i>0 && nums[i]==nums[i-1])
 9                 continue;
10             int l = i+1, r = nums.size()-1;
11             while(l < r)
12             {
13                 int sum = nums[i] + nums[l] + nums[r];
14                 if(sum > 0)
15                     r--;
16                 else if(sum < 0)
17                     l++;
18                 else
19                 {
20                     res.push_back(vector<int> {nums[i], nums[l], nums[r]});
21                     //防止重复
22                     while(l+1 < nums.size() && nums[l] == nums[l+1]) l++;
23                     while(r-1 >= 0 && nums[r] == nums[r-1]) r--;
24                     l++; r--;
25                 }
26             }
27         }
28         return res;  
29     }
30 };