https://leetcode.com/problems/3sum/
题目：
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(n^2 logn). 太慢了
1 class Solution { 2 public: 3 vector > threeSum(vector & nums) { 4 set > res; 5 vector > output; 6 vector sol; 7 sort(nums.begin(),nums.end()); //sort first 8 int i,j,k,t,x,n=nums.size(); 9 for(i=0;i > :: iterator iter;23 for(iter=res.begin();iter!=res.end();iter++){24 output.push_back(*iter);25 }26 return output;27 }28 int findSol(int target,vector
nums,int begin,int end){29 if(nums[begin]==target)30 return begin;31 if(nums[end]==target)32 return end; 33 if(nums[begin]>target||nums[end]
target){41 end=mid-1;42 }43 else44 begin=mid+1;45 }46 return -1;47 }48 }; 方法二： 一层循环加two sum思想（https://leetcode.com/problems/two-sum/）,O(n^2).
1 class Solution { 2 public: 3 vector > threeSum(vector & nums) { 4 sort(nums.begin(),nums.end()); 5 vector > res; 6 int i,t,a,b,k,n=nums.size(); 7 for(i=0;i t){17 b--;18 }19 else{20 vector sol(3,0);21 sol[0]=nums[i];22 sol[1]=nums[a];23 sol[2]=nums[b];24 res.push_back(sol);25 while (a < b && nums[a] == sol[1]) 26 a++;27 while (a < b && nums[b] == sol[2]) 28 b--;29 }30 }31 while (i + 1 < nums.size() && nums[i + 1] == nums[i]) 32 i++;33 }34 35 //deduplicate, but it is so slow!36 //sort(res.begin(), res.end()); 37 //res.erase(unique(res.begin(), res.end()), res.end());38 return res;39 }40 };