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)
这题各种面熟，先来暴力的吧。因为要求abcd是递增的，所以可以先将num排序以后再爆，嗯。
我擦咧闹不住暴破法(Time Limit Exceed)：
1 vector<vector<int> > fourSum(vector<int> &num, int target) { 2 vector<vector<int>>result; 3 if (num.size() < 4) return result; 4 sort(num.begin(), num.end()); 5 for (int i=0; i<num.size()-3; i++){ 6 for (int j=i+1; j<num.size()-2; j++){ 7 for (int k=j+1; k<num.size()-1; k++){ 8 for (int v=k+1; v<num.size(); v++){ 9 if (num[i]+num[j]+num[k]+num[v] == target){ 10 vector<int>tmp; 11 tmp.push_back(num[i]); 12 tmp.push_back(num[j]); 13 tmp.push_back(num[k]); 14 tmp.push_back(num[v]); 15 result.push_back(tmp); 16 } 17 } 18 } 19 } 20 } 21 return result; 22 }
O(n^4)就是个娱乐，别说大集合没戏，连稍微大一点的集合都过不了的。
看看优化，可以把最后一层循环n变成logn, 思想是最后一层循环实际上是为了从 [k+1, num.size()) 中找到一个数x且x=target - (num[i]+num[j]+num[k]) 。这样我们就可以用二分查找代替遍历，所以原本的O(n^4)就变成了O(n^3 logn)
复杂度依然是难以接受的，但至少比n^4要好一丢丢，期待进一步优化...
我擦咧稍微闹得住一丢丢暴破法(Time Limit Exceed):
1 vector<vector<int> > fourSum(vector<int> &num, int target) { 2 vector<vector<int>>result; 3 if (num.size() < 4) return result; 4 sort(num.begin(), num.end()); 5 for (int i=0; i<num.size()-3; i++){ 6 for (int j=i+1; j<num.size()-2; j++){ 7 for (int k=j+1; k<num.size()-1; k++){ 8 if (binary_search(num.begin()+k+1, num.end(), target - num[i]-num[j]-num[k])){ 9 vector<int>tmp; 10 tmp.push_back(num[i]); 11 tmp.push_back(num[j]); 12 tmp.push_back(num[k]); 13 tmp.push_back(target - num[i]-num[j]-num[k]); 14 result.push_back(tmp); 15 } 16 } 17 } 18 } 19 return result; 20 }
通过一些挣扎看了一些答案，虽然还是n^3但是500ms可以通过大集合。
1 vector<vector<int> > fourSum(vector<int> &num, int target) { 2 vector<vector<int>>result; 3 if (num.size() < 4) return result; 4 sort(num.begin(), num.end()); 5 for (int i=0; i<num.size()-3; i++){ 6 if (i && num[i] == num[i-1]) continue; 7 for (int j=i+1; j<num.size()-2; j++){ 8 if (j>i+1&&num[j]==num[j-1])continue; 9 for (int k=j+1; k<num.size()-1; k++){ 10 if (k>j+1&& num[k]==num[k-1])continue; 11 int tarV = target-(num[i]+num[j]+num[k]); 12 if (num[k+1] > tarV || num[num.size()-1] < tarV)continue; 13 if (binary_search(num.begin()+k+1, num.end(), target - num[i]-num[j]-num[k])){ 14 vector<int>tmp; 15 tmp.push_back(num[i]); 16 tmp.push_back(num[j]); 17 tmp.push_back(num[k]); 18 tmp.push_back(target - num[i]-num[j]-num[k]); 19 result.push_back(tmp); 20 } 21 } 22 } 23 } 24 return result; 25 }
有几点需要优化，一是每层遍历的时候注意过滤掉重复的选择（这一轮跟上一轮选了一样的数）。 还有第12行的过滤也很重要，判断最后一个数的第一个可能是否大于我们想要的结果，大于的话说明之后的每个数都要比它大，因为num已经被排序了。
同理，还要判断num的最后一个数是否小于tar,如果小于的话也没必要再二分找了，根本不存在。
这题还有更为优化的n^2法，貌似使用hash， 把内层的两两之和遍历出来以后，同索引放在hash map 里。思路大概是这样，等我之后验证。