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)
解法1：首先想到肯定是暴力破解，时间复杂度O(n^4)，肯定不满足时间要求Time Limit Exceeded
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); vector< vector<int> > res; for(int i = 0; i < n - 4; i++) { for(int j = i + 1; j < n - 3; j++) { for(int k = j + 1; k < n - 2; k++) { for(int l = k + 1; l < n - 1; l++) { if(nums[i] + nums[j] + nums[k] + nums[l] == target) { vector<int> tmp; tmp.push_back(nums[i]); tmp.push_back(nums[j]); tmp.push_back(nums[k]); tmp.push_back(nums[l]); sort(tmp.begin(), tmp.end()); if(find(res.begin(), res.end(), tmp) == res.end()) res.push_back(tmp); } } } } } return res; } };
解法2：对比前面的问题3Sum，解法2将3Sum问题归约为2Sum问题解决，因此想到4Sum问题类似，可以归约为3Sum或者2Sum问题解决。时间复杂度是O(n^3)。
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); set< vector<int> > res; sort(nums.begin(), nums.end()); for(int i = 0; i < n - 3; i++) { for(int j = i + 1; j < n - 2; j++) { int left = j + 1, right = n - 1; while(left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if(target == sum) { vector<int> tmp; tmp.push_back(nums[i]); tmp.push_back(nums[j]); tmp.push_back(nums[left]); tmp.push_back(nums[right]); res.insert(tmp); left++; right--; } else if(target < sum) right--; else left++; } } } return vector< vector<int> >(res.begin(), res.end()); } };
解法3：先将数组排序，然后三层循环确定三个数，最后一个数target=target-nums[i]-nums[j]-nums[k]在数组剩下的元素中使用二分查找进行搜索，时间复杂度O(n^3logn)
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); set< vector<int> > res; sort(nums.begin(), nums.end()); for(int i = 0; i < n - 3; i++) { for(int j = i + 1; j < n - 2; j++) { for(int k = j + 1; k < n - 1; k++) { int tmp = target - nums[i] - nums[j] - nums[k]; int left = k + 1, right = n - 1; while(left <= right) { int mid = (left + right) >> 1; if(tmp = nums[mid]) { vector<int> tmpRes; tmpRes.push_back(nums[i]); tmpRes.push_back(nums[j]); tmpRes.push_back(nums[k]); tmpRes.push_back(nums[mid]); res.insert(tmpRes); left++; right--; } else if(tmp < nums[mid]) right = mid - 1; else left = mid + 1; } } } } return vector< vector<int> >(res.begin(), res.end()); } };
这种解法仍然会出现Time Limit Exceeded。
解法4：LeetCode的Hide Tags提示可以使用Hash Table进行优化，以空间换时间。a+b+c+d=target可以看做(a+b)+(c+d)=target，即先分别求两组两个数之后，然后判断这两个和之和是否等于target。具体的，先对数组做预处理，算出所有元素的两两之和（时间复杂度O(n^2)），最后对这些和求解2Sum问题（使用Hash Table的2Sum问题时间复杂度为O(1)）。时间复杂度为O(n^2)，为预处理时枚举所有两两之和所花时间。
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); set< vector<int> > res; sort(nums.begin(), nums.end()); map<int, set< pair<int, int> > > twoSum; for (int i = 0; i < n - 1; i++) //预处理求所有的两两之和 { for (int j = 0; j < n; j++) { int sum = nums[i] + nums[j]; if (nums[i] > nums[j]) twoSum[sum].insert(make_pair(nums[j], nums[i])); else twoSum[sum].insert(make_pair(nums[i], nums[j])); } } map<int, set< pair<int, int> > >::iterator iter; map<int, set< pair<int, int> > >::iterator beg = twoSum.begin(); map<int, set< pair<int, int> > >::iterator end = twoSum.end(); for (iter = beg; iter != end; iter++) //求和的2Sum问题 { int tmp = target - iter->first; map<int, set< pair<int, int> > >::iterator another = twoSum.find(tmp); if (another != end) { for (set< pair<int, int> >::iterator iter1 = iter->second.begin(); iter1 != iter->second.end(); iter1++) { for (set< pair<int, int> >::iterator iter2 = another->second.begin(); iter2 != another->second.end(); iter2++) res.insert(vector<int>{ iter1->first, iter1->second, iter2->first, iter2->second }); } } }
return vector< vector<int> >(res.begin(), res.end()); } };
上面代码还是会出现Time Limit Exceeded，改进如下：
class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { int n = num.size(); vector< vector<int> > res; unordered_map<int, vector< pair<int, int> > >pairs; pairs.reserve(n * n); sort(num.begin(), num.end()); for(int i = 0; i < n; i++) for(int j = i + 1 ; j < n; j++) pairs[num[i] + num[j]].push_back(make_pair(i, j)); for(int i = 0; i < n - 3; i++) { if(i != 0 && num[i] == num[i - 1]) continue; //防止第一个元素重复 for(int j = i + 1; j < n - 2; j++) { if(j != i + 1 && num[j] == num[j - 1]) continue; //防止第二个元素重复 if(pairs.find(target - num[i] - num[j]) != pairs.end()) { vector< pair<int, int> >& sum2 = pairs[target - num[i] - num[j]]; bool isFirstPush = true; for(int k = 0; k < sum2.size(); k++) { if(sum2[k].first <= j) continue; //保证所求的四元组的数组下标是递增的 if(isFirstPush || (res.back())[2] != num[sum2[k].first]) { res.push_back(vector<int>{num[i], num[j], num[sum2[k].first], num[sum2[k].second]}); isFirstPush = false; } } } } } return res; } };