首页 > 代码库 > three Sum
three Sum
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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。