首页 > 代码库 > leetcode第一刷_4Sum
leetcode第一刷_4Sum
用暴力水过了两个,正在沾沾自喜,当看到连续加的规模增加到4时,眼泪直接掉下来了,新想这下我这水货原形毕露了,没想到。。
我抱着试试看的心态,又写了一种水水的暴力解,每次固定前面的两个节点,后面的两个按照twosum那套来搞,搞完了移动之前固定的右边的那个点,最后再移动固定的左边的那个点,居然也过了。。
刚想起来其实twosum有一种很优雅的解法,建一个hash表,从头扫描数组,遇到一个数,查找这个数与target的差在不在hash表里,如果在,说明这两个数找到了,他们的下标分别是找到的那个数在hash表中的索引,以及当前这个数的索引。如果不在hash表里,那就把这个差放入hash表。比头尾双指针看上去高端一些。
class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > res; if(num.size()<4) return res; sort(num.begin(), num.end()); for(int i=0;i<num.size()-3;i++){ if(i&&num[i] == num[i-1]) continue; int j = i+1; int k = num.size()-1; while(j<k){ if(j>i+1&&num[j]==num[j-1]) {j++; continue;} if(k<num.size()-1&&num[k]==num[k+1]) {k--; continue;} int l = j+1; int m = k; while(l<m){ if(l>j+1&&num[l]==num[l-1]) {l++; continue;} if(m<k&&num[m]==num[m+1]) {m--; continue;} int sum = num[i]+num[j]+num[l]+num[m]; if(sum < target) l++; else if(sum>target) m--; else{ vector<int> tpres; tpres.push_back(num[i]); tpres.push_back(num[j]); tpres.push_back(num[l]); tpres.push_back(num[m]); //cout<<num[i]<<" "<<num[j]<<" "<<num[l]<<" "<<num[m]<<endl; res.push_back(tpres); l++; } } j++; } } return res; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。