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). 太慢了

 class Solution {

 public:

     vector<vector<int>> threeSum(vector<int>& nums) {

         set<vector<int>> res;

         vector<vector<int>> output;

         vector<int> sol;

         sort(nums.begin(),nums.end());    //sort first

         int i,j,k,t,x,n=nums.size();

         for(i=;i<n;i++){

             for(j=i+;j<n-;j++){

                 t=nums[i]+nums[j];

                 x=findSol(-t,nums,j+,n-);

                 if(x!=-){

                     sol.clear();

                     sol.push_back(nums[i]);

                     sol.push_back(nums[j]);

                     sol.push_back(nums[x]);

                     res.insert(sol);

                 }

             }

         }

         set<vector<int>> :: iterator iter;

         for(iter=res.begin();iter!=res.end();iter++){

             output.push_back(*iter);

         }

         return output;

     }

     int findSol(int target,vector<int> nums,int begin,int end){

         if(nums[begin]==target)

             return begin;

         if(nums[end]==target)

             return end;

         if(nums[begin]>target||nums[end]<target)

             return -;

         int mid;

         while(begin<=end){

             mid=(begin+end)/;

             if(nums[mid]==target)

                 return mid;

             else if(nums[mid]>target){

                 end=mid-;

             }

             else

                 begin=mid+;

         }

         return -;

     }

 };

方法二：一层循环加two sum思想（https://leetcode.com/problems/two-sum/）,O(n^2).

 class Solution {

 public:

     vector<vector<int>> threeSum(vector<int>& nums) {

         sort(nums.begin(),nums.end());

         vector<vector<int>> res;

         int i,t,a,b,k,n=nums.size();

         for(i=;i<n-;i++){

             t=-nums[i];

             a=i+;

             b=n-;

             while(a<b){

                 k=nums[a]+nums[b];

                 if(k<t){

                     a++;

                 }

                 else if(k>t){

                     b--;

                 }

                 else{

                     vector<int> sol(,);

                     sol[]=nums[i];

                     sol[]=nums[a];

                     sol[]=nums[b];

                     res.push_back(sol);

                     while (a < b && nums[a] == sol[])

                         a++;

                     while (a < b && nums[b] == sol[])

                         b--;

                  }

             }

             while (i +  < nums.size() && nums[i + ] == nums[i])

             i++;

         }

         //deduplicate, but it is so slow!

         //sort(res.begin(), res.end());

         //res.erase(unique(res.begin(), res.end()), res.end());

         return res;

     }

 };

巴特西

LeetCode(15)题解--3Sum

最新文章

热门文章