【数组、算法】 LEETCODE15 找数组中三个数和为0的所有组合
发布时间:2020-12-15 07:45:44 所属栏目:Java 来源:网络整理
导读:// 解法一,map将数组分成n,p三组,寻找9(0,0),(n,p)(n,n,p)和(p,p,n)的组合,但是因为不可重复,所以最后两种组合比较麻烦,复杂度是O(n^2),遍历多次,最后两个case TLE class Solution { public : vector vector int threeSum(vector int nums) { map int
//解法一,map将数组分成n,p三组,寻找9(0,0),(n,p)(n,n,p)和(p,p,n)的组合,但是因为不可重复,所以最后两种组合比较麻烦,复杂度是O(n^2),遍历多次,最后两个case TLE class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { map<int,int> ne; map<int,int> po; int nne=0,npo=0,zero=0; vector<vector<int>> answer; for(int i=0;i<nums.size();i++){ if(nums[i]>0){ po[nums[i]]++; npo++; } else if(nums[i]<0){ ne[nums[i]]++; nne++; } else zero++; } if(zero>=3){ vector<int> v; v.push_back(0); v.push_back(0); v.push_back(0); answer.push_back(v); } if(nne&&npo){ if(zero){ for(map<int,int>::iterator it=ne.begin();it!=ne.end();it++){ if(po[-it->first]){ vector<int> v; v.push_back(it->first); v.push_back(0); v.push_back(-it->first); answer.push_back(v); } else po.erase(-it->first); } } if(nne>=2){ for(map<int,int>::iterator i=ne.begin();i!=ne.end();i++){ for(map<int,int>::iterator j=i;j!=ne.end();j++){ if(i->first==j->first && i->second<2) continue; else{ int left= -((i->first)+(j->first)); if(po[left]){ vector<int> v; v.push_back(i->first); v.push_back(j->first); v.push_back(left); answer.push_back(v); } else po.erase(left); } } } } if(npo>=2){ for(map<int,int>::iterator i=po.begin();i!=po.end();i++){ for(map<int,int>::iterator j=i;j!=po.end();j++){ if(i->first==j->first && i->second<2) continue; else{ int left=-(i->first+j->first); if(ne[left]){ vector<int> v; v.push_back(i->first); v.push_back(j->first); v.push_back(left); answer.push_back(v); } else ne.erase(left); } } } } } return answer; } }; //解法2,每有一个数,去找符合条件的另外两个数。把数组排好序,可以利用二分法的思想,避免枚举所有其他两个数的组合。排序O(nlogn),后面的遍历约为O(n^2), (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |