LeetCode(15)题解--3Sum

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<vector<int>> threeSum(vector<int>& nums) {
 4         set<vector<int>> res;
 5         vector<vector<int>> output;
 6         vector<int> sol;
 7         sort(nums.begin(),nums.end());    //sort first
 8         int i,j,k,t,x,n=nums.size();
 9         for(i=0;i<n;i++){
10             for(j=i+1;j<n-1;j++){
11                 t=nums[i]+nums[j];
12                 x=findSol(-t,nums,j+1,n-1);
13                 if(x!=-1){
14                     sol.clear();
15                     sol.push_back(nums[i]);
16                     sol.push_back(nums[j]);
17                     sol.push_back(nums[x]);
18                     res.insert(sol);
19                 }
20             }
21         }
22         set<vector<int>> :: 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<int> 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)
34             return -1;
35         int mid;
36         while(begin<=end){
37             mid=(begin+end)/2;
38             if(nums[mid]==target)
39                 return mid;
40             else if(nums[mid]>target){
41                 end=mid-1;
42             }
43             else
44                 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<vector<int>> threeSum(vector<int>& nums) {
 4         sort(nums.begin(),nums.end());
 5         vector<vector<int>> res;
 6         int i,t,a,b,k,n=nums.size();
 7         for(i=0;i<n-2;i++){
 8             t=-nums[i];
 9             a=i+1;
10             b=n-1;
11             while(a<b){
12                 k=nums[a]+nums[b];
13                 if(k<t){
14                     a++;
15                 }
16                 else if(k>t){
17                     b--;
18                 }
19                 else{
20                     vector<int> 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 };