首页 > 代码库 > leetcode-3Sum-15
leetcode-3Sum-15
输入一个数组,任选三个数求和,和为0的所有组合,不能重复,即,-1,0,1这样的三元组只能出现一次。
解法:类似两个数求和的方法,先排序,然后首尾指针法,但这里要求三个数,所以还是得遍历一遍,因此第一个数遍历,剩下两个数用首尾指针法,ON^2
对于重复三元组的处理:本来想把所有结果先放入set<node> 里,然后在复制到vector<vector<int> >中返回,但不知道为何不能去重。先马再说
1 class Solution { 2 // private: 3 // struct node{ 4 // int a,b,c; 5 // node(){} 6 // node(int x,int y,int z):a(x),b(y),c(z){} 7 // bool operator<(const node &n)const{ 8 // if(a==n.a&&b==n.b&&c==n.c) return false; 9 // return true;10 // }11 // };12 public:13 vector<vector<int> > threeSum(vector<int>& nums) {14 vector<vector<int> > v;15 if(nums.size()<3) return v;16 sort(nums.begin(),nums.end());17 //set<node> s;18 for(int i=0;i<nums.size();i++){19 if(i>0&&nums[i]==nums[i-1]) continue;20 int j=i+1,k=nums.size()-1;21 while(j<k){22 int sum=nums[i]+nums[j]+nums[k];23 if(sum==0){24 vector<int> vv;25 vv.push_back(nums[i]);26 vv.push_back(nums[j]);27 vv.push_back(nums[k]);28 v.push_back(vv);29 // node no(nums[i],nums[j],nums[k]);30 // if(s.find(no)==s.end()){31 // //cout<<"ha"<<endl;32 // s.insert(no);33 // }34 int tmp=nums[j];35 while(nums[j]==tmp) j++;36 continue;37 }38 if(sum<0) j++;39 else k--;40 }41 }42 // for(set<node>::iterator it=s.begin();it!=s.end();it++){43 // vector<int> vv;44 // vv.push_back(it->a);45 // vv.push_back(it->b);46 // vv.push_back(it->c);47 // v.push_back(vv);48 // }49 // cout<<"*********"<<endl;50 // for(int i=0;i<v.size();i++){51 // cout<<v[i][0]<<" "<<v[i][1]<<" "<<v[i][2]<<endl;52 // }53 return v;54 }55 };
leetcode-3Sum-15
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。