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: The solution set must not contain duplicate triplets.
思路：排序O(nlgn)，然后枚举一个元素O(n)，对于每个元素，在剩下的区间中 two pointer O(n)
整体复杂度 O(n^2)。
hash的解法以后补。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 16时07分00秒
4File Name :15.cpp
5************************************************ */
6class Solution {
7public:
8 set<vector<int> >se;
9 vector<vector<int> >res;
10 vector<vector<int>> threeSum(vector<int>& nums) {
11 sort(nums.begin(),nums.end());
12 int n = nums.size();
13 for ( int i = 0 ; i <=n-3 ; i++)
14 {
15 int head = i+1;
16 int tail = n-1;
17 int tar = -nums[i];
18 while (head<tail)
19 {
20 if (nums[head]+nums[tail]==tar)
21 {
22 vector<int>tmp;
23 tmp.push_back(nums[i]);
24 tmp.push_back(nums[head]);
25 tmp.push_back(nums[tail]);
26 se.insert(tmp);
27 head++;
28 tail--;
29 }
30 else if (nums[head]+nums[tail]<tar) head++;
31 else tail--;
32 }
33 }
34 for ( auto &it : se)
35 res.push_back(it);
36 return res;
37 }
38};