首页 > 代码库 > three Sum

three Sum

2024-08-01 03:58:43   232人阅读

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.

 

 1 class Solution { 2 public: 3     vector<vector<int> > threeSum(vector<int> &num) { 4         vector<int> NumCopy(num); 5         vector<vector<int> > returnvct; 6         sort(NumCopy.begin(),NumCopy.end()); 7         int m=0,cnt=0; 8         while(NumCopy[m]<0) 9             ++m;10         int f = m,j=m;11         while(NumCopy[f] == 0){12             ++f;13             ++cnt;14         }15         if(cnt>=3){16             f = m+cnt-1;17             j = m+cnt-2;18         }19         for(int i=0;f<NumCopy.size();++f){20             int tempi =i,tempj =j;21             int sum = -1 * (NumCopy[i]+NumCopy[j]);22             while( sum > NumCopy[f]&& i<j ){23                 ++i;24                 sum = -1* (NumCopy[i]+ NumCopy[j]);25             }26             if(sum == NumCopy[f]){27                 vector<int> tmp;28                 tmp.push_back(i);29                 tmp.push_back(j);30                 tmp.push_back(f);31                 returnvct.push_back(tmp);32             }33             34             while(sum < NumCopy[f] && i<j){35                 --j;36                 sum = -1 * (NumCopy[i]+ NumCopy[j]);37             }38             i = tempi;39             j= tempj;40         }41         return returnvct;42     }43 };


利用昨天twoSum的方法 将a+b+c =0 变成 a+b =-c;数组 以0为界限 分为前后两部分。

可是又超时了::>_<:: 。

three Sum


联系
我们