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: 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] ]
本题问一个数组中哪四个数加起来的和等于target,相当于LeetCode 3Sum的升级版,但是方法和3Sum是一样的,先枚举前两个数,对于后两个数,用首尾指针来求和。
一开始我的代码完全按照LeetCode 3Sum来写,先求最大最小值,然后用桶来hash,最后三层循环,代码如下:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int min_v = INT_MAX, max_v = INT_MIN; for(int i = 0; i < nums.size(); ++i) { if(nums[i] < min_v)min_v = nums[i]; if(nums[i] > max_v)max_v = nums[i]; } vector<int> hash(max_v - min_v + 1, 0); for(int i = 0; i < nums.size(); ++i){ ++hash[nums[i] - min_v]; } vector<vector<int>> ans; for(int i = 0; i < hash.size(); ++i){ if(hash[i] == 0)continue; --hash[i]; for(int j = i; j < hash.size(); ++j){ if(hash[j] == 0) continue; --hash[j]; int u = j, v = hash.size() - 1; while(u <= v){ while(u <= v && hash[u] == 0) ++u; if(u > v) break; --hash[u]; while(u <= v && hash[v] == 0) --v; if(u > v){ ++hash[u]; break; } --hash[v]; int sum = i + j + u + v + 4 * min_v; ++hash[u]; ++hash[v]; if(sum == target){ ans.push_back({i + min_v, j + min_v, u + min_v, v + min_v}); ++u; --v; } else if(sum < target) ++u; else --v; } ++hash[j]; } ++hash[i]; } return ans; } };
但是本代码提交TLE,看了一下,最后一个样例中,最小值有-236727523之小,最大值有91277418之大,导致hash数组太大了,从而无效的空for循环太多,最终TLE。
后来改用排序代替hash,需要注意为了防止重复结果,对四个数都要有去重的操作。代码如下:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> ans; int n = nums.size(); for(int i = 0; i < n - 3; ++i){ if(i > 0 && nums[i] == nums[i-1])continue; // 防止nums[i]重复 for(int j = i + 1; j < n - 2; ++j){ if(j > i + 1 && nums[j] == nums[j-1])continue; // 防止nums[j]重复 int u = j + 1, v = n - 1; while(u < v){ int sum = nums[i] + nums[j] + nums[u] + nums[v]; if(sum == target){ ans.push_back({nums[i], nums[j], nums[u], nums[v]}); int k = u + 1; while(k < v && nums[k] == nums[u]) ++k; // 防止nums[u]重复 u = k; k = v - 1; while(k > u && nums[k] == nums[v]) --k; // 防止nums[v]重复 v = k; } else if(sum < target) ++u; else --v; } } } return ans; } };
本代码提交AC,用时39MS。
还有一种思路是,先对数组中两数之和Hash,然后枚举两个两数之和,转换为类似Two Sum的方法,时间复杂度为。
Pingback: LeetCode 4Sum II | bitJoy > code