首页 > 代码库 > leetcode-3Sum-15

leetcode-3Sum-15

2024-08-11 07:21:17   212人阅读

输入一个数组，任选三个数求和，和为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


联系
我们