Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
Array Hash Table Two Pointers 题目是给一个数组，从中选取4个，输入全部组合，其和为target。
题目操作起来好麻烦，调试了挺久，比较麻烦的是会有重复，时间上面需要考虑。
最直接的是
- 排序
- 4层遍历
这个时间是O(n^4)，这时间不用看也知道超时了。提升的想法是确定3个之后，使用二分法查找提升速度。
- 排序
- 3层遍历
- 二分法查找剩下的target - a-b-c
1 class Solution { 2 public: 3 vector<vector<int> > fourSum(vector<int> &num, int target) { 4 sort(num.begin(),num.end()); 5 vector<vector<int> > ret; 6 for(int a=0;a<num.size();){ 7 for(int b=a+1;b<num.size();){ 8 for(int c=b+1;c<num.size();){ 9 if(binary_search(num.begin()+c+1,num.end(),target-num[a]-num[b]-num[c])) 10 ret.push_back({num[a],num[b],num[c],target-num[a]-num[b]-num[c]}); 11 c++; 12 while(c<num.size()&&num[c-1]==num[c]) c++; 13 } 14 b++; 15 while(b<num.size()&&num[b-1]==num[b]) b++; 16 } 17 a++; 18 while(a<num.size()&&num[a-1]==num[a]) a++; 19 } 20 return ret; 21 } 22 };
这个时间是O(n^3 logn)，我写了这个，超时了，那么还需要提升时间，假如有两个数确定了，问题变为从数组中找两数，之和为定值，如果这个查找在有序数列上设左右指针，那么查找时间只需要O(n)，这样时间便为 O(n^3)
- 排序
- 从左遍历，每次遍历进入3
- 从右遍历，每次进入4
- 设定左右索引，指向 2、3 还没遍历的数组框左右，判断索引数之和与temp_target，大了右索引左移，小了左索引右移，符合的数放入return。
这个没有写，如果还需要提高时间，那么这样想，因为是4个数之和，可以看成两组数之和，每组两个数，这样如果知道了每两个数之和，问题如上面的转换，这样时间便是O(n^2)，不过空间就需要大很多。维持如下的结构：
| -2 | -1 | 0 | 1 | 2 |
| ↓ | ↓ | ↓ | ↓ | ↓ |
| -2,0 | -1,0 | 0,0 | 0,1 | 0,2 |
| -1,-1 | -2,1 | -2,2 | 2,-1 | |
| -1,1 | ||||
维持这样的结构，第一行为组的和，然后指向所有的组合，因为c++ map 是会自动排序的，所以创建 map<int,pari<int,int> > > 这样的一个表便可以了，然后就是剩下判断问题了，如只有 -2 0 2 各一个，但是 -2 2 是可以的，所以需要考虑个数问题。
我用了unorder_map，并没有通过双向收缩来实现，所以判断起来比较麻烦，不过map 在初始化的时候，时间需要logn，所以这样的总体时间是O(n^2logn)，这个也是discuss 普遍时间。而使用unorder_map，我的时间是O(n^2 + n*Maxlen(bucket)^2)，上图就是Maxlen(bucket)=3，在n较大是较优，注意是+号，毕竟比较难表达，应该会接近O(n^2)。
- 计算两数之和，放入mp 中
- 统计各数的个数，使用map<int,int> cnt 存储
- 遍历mp
- 判断 target- val1 是否在mp 中，否继续遍历，这个时间是O(1)
- 存在的话，如果val1 > val2，continue，为了避免重复
- 遍历bucket1 中的组合
- 遍历bucket2 中的组合，如果 max(group1)<=min(group2)则进入下一步，这是为了避免重复，等号为了 0,0,0,0情况
- 通过cnt 判断数的个数够不够，够的放入return。
- 结束
最终代码如下：
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <iterator> 5 #include <unordered_map> 6 using namespace std; 7 /** 8 class Solution { 9 public: 10 vector<vector<int> > fourSum(vector<int> &num, int target) { 11 sort(num.begin(),num.end()); 12 vector<vector<int> > ret; 13 for(int a=0;a<num.size();){ 14 for(int b=a+1;b<num.size();){ 15 for(int c=b+1;c<num.size();){ 16 if(binary_search(num.begin()+c+1,num.end(),target-num[a]-num[b]-num[c])) 17 ret.push_back({num[a],num[b],num[c],target-num[a]-num[b]-num[c]}); 18 c++; 19 while(c<num.size()&&num[c-1]==num[c]) c++; 20 } 21 b++; 22 while(b<num.size()&&num[b-1]==num[b]) b++; 23 } 24 a++; 25 while(a<num.size()&&num[a-1]==num[a]) a++; 26 } 27 return ret; 28 } 29 }; 30 */ 31 class Solution { 32 public: 33 vector<vector<int> > fourSum(vector<int> &num, int target) { 34 sort(num.begin(),num.end()); 35 vector<vector<int> > ret; 36 unordered_map<int,vector<pair<int,int> > > mp; 37 unordered_map<int,int> cnt; 38 for(unsigned int a=0;a<num.size();){ 39 for(unsigned int b=a+1;b<num.size();){ 40 mp[num[a]+num[b]].push_back(pair<int,int> {num[a],num[b]}); 41 b++; 42 while(b<num.size()&&num[b-1]==num[b]) b++; 43 } 44 a++; 45 while(a<num.size()&&num[a-1]==num[a]) a++; 46 } 47 for(unsigned int a = 0;a<num.size();a++) 48 cnt[num[a]]++; 49 // for(unordered_map<int,int>::iterator it=cnt.begin();it!=cnt.end();it++) 50 // cout<<it->first<<":"<<it->second<<endl; 51 // for(unordered_map<int,vector<pair<int,int> > >::iterator it1=mp.begin();it1!=mp.end();it1++){ 52 // cout<<it1->first<<":"<<endl; 53 // for(int i=0;i<it1->second.size();i++) 54 // cout<<it1->second[i].first<<" "<<it1->second[i].second<<endl; 55 // } 56 57 for(unordered_map<int,vector<pair<int,int> > >::iterator it1=mp.begin();it1!=mp.end();it1++){ 58 // cout<<it1->first<<endl; 59 unordered_map<int,vector<pair<int,int> > >::iterator it2=mp.find(target - it1->first); 60 if(it2!=mp.end()){ 61 // cout<<it1->first<<it2->first<<endl; 62 // cout<<it1->second.size()<<it2->second.size()<<endl; 63 if(it1->first > it2->first) continue; 64 for(int i=0;i<it1->second.size();i++){ 65 for(int j=0;j<it2->second.size();j++){ 66 int a = it1->second[i].first,b = it1->second[i].second,c = it2->second[j].first,d = it2->second[j].second; 67 if(max(a,b)<=min(c,d)){ 68 bool flag = true; 69 cnt[a]--; 70 cnt[b]--; 71 cnt[c]--; 72 cnt[d]--; 73 if(cnt[a]<0||cnt[b]<0||cnt[c]<0||cnt[d]<0) flag = false; 74 cnt[a]++; 75 cnt[b]++; 76 cnt[c]++; 77 cnt[d]++; 78 // cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<flag<<endl; 79 if(flag){ 80 vector<int> tmp = {a,b,c,d}; 81 sort(tmp.begin(),tmp.end()); 82 ret.push_back(tmp); 83 } 84 } 85 } 86 } 87 } 88 } 89 return ret; 90 } 91 }; 92 93 94 95 96 int main() 97 { 98 vector<int > num = {1,0,-1,0,-2,2}; 99 Solution sol; 100 vector<vector<int> > ret = sol.fourSum(num,0); 101 for(unsigned int i=0;i<ret.size();i++){ 102 copy(ret[i].begin(),ret[i].end(),ostream_iterator<int>(cout," ")); 103 cout<<endl; 104 } 105 return 0; 106 }
需要注意的是mp 中的group 是不能重复的，就是如果有 <-1,0>那么便不会有<0,-1>。