题目描述:给定一个有n个整数的数组S和目标值target,找到其中所有由四个数a、b、c、d组成,使得a + b + c + d = target 的四元组。如:
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]
]
分析:与 3sum 的思路一样,先排序再左右夹逼,由于多一层循环复杂度O(n^3)。或者用 hashmap 先缓存两个数的和,这也可用于3sum, 最终复杂度O(n^3)。
方法一:先排序再左右夹逼,时间复杂度O(n^3),空间O(1)。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector< vector<int> > ans;
if (nums.size() < 4) return ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i ++)
{
for (int j = i + 1; j < nums.size() - 2; j ++)
{
int l = j + 1, r = nums.size() - 1;
while(l < r)
{
if (nums[i] + nums[j] + nums[l] + nums[r] < target)
l ++;
else if (nums[i] + nums[j] + nums[l] + nums[r] > target)
r --;
else
{
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
l ++;
r --;
}
}
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end()); //erase函数删除两迭代器之间的元素,unique返回的是重排后第一个多余元素的位置
return ans;
}
};
方法二:先用 hashmap 缓存两个数的和,平均O(n^2 ),最坏O(n^4 ),空间复杂度O(n^2)。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector< vector<int> > ans;
if (nums.size() < 4) return ans;
sort(nums.begin(), nums.end());
unordered_map<int, vector<pair<int, int> > > mp; //两数和为键,这两数下标对为值
for (int i = 0; i < nums.size(); i ++)
for (int j = i + 1; j < nums.size(); j ++)
mp[nums[i] + nums[j]].push_back(pair<int, int>(i, j));
for (int i = 0; i < nums.size(); i ++)
{
for (int j = i + 1; j < nums.size(); j ++)
{
int gap = target - nums[i] - nums[j];
if (mp.find(gap) == mp.end())
continue;
auto vec = mp[gap];
for (int k = 0; k < vec.size(); k++)
{
if (i <= vec[k].second) //有重叠,因为存入map时pair中小下标在前,大下标在后。i < j, vec[k].first < vec[k].second。改为 (j >= vec[k].first) 也可通过。保证a != c && a != d && b != c && b != d
continue;
ans.push_back({nums[ vec[k].first ], nums[ vec[k].second ], nums[i], nums[j]}); //a≤b≤c≤d
}
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end()); //去重,不能包含重复的四元组
return ans;
}
};
网友评论