Question：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)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {}
}
1 题目思路分析##
本题与3Sum的基本思路相同，都是先排序，然后先取好前两个数，最后两个数来夹逼。
1.1 基本思路( O(n^3) )###
按照基本思路，有两个版本，一个自己写的，一个是书里的，自己写的结果一个测试用例超时（64ms）， 书里的（44ms）过了，郁闷。
1.1.1 自己写的
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort( nums.begin(), nums.end() );
int size= nums.size();
auto last=nums.end();
auto start=nums.begin();
vector<vector<int>>result;
if(size<4) return result;
for(auto h=start; h<(last-3); h++)
{
if( h!=start && *h == *(h-1) ) continue;
for (auto i=h+1; i<(last-2); i++)
{
if ( i!= (h+1) && *i==*(i-1) ) continue;
auto j=i+1;
auto k=last-1;
while (j<k)
{
if (*h + *i + *j + *k < target)
{
j++;
while (*j == *(j-1) && j<k ) j++;
}
else if(*h + *i + *j + *k > target)
{
k--;
while (*k == *(k+1) && j<k) k--;
}
else
{
result.push_back({*h, *i, *j, *k});
j++;
k--;
while (*j==*(j-1) && *k==*(k+1) && j<k) j++;
}
}
}
}
return result;
}
};
1.1.2 书上的
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& num, int target)
{
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
auto last = num.end();
for (auto a = num.begin(); a < prev(last, 3); ++a)
{
for (auto b = next(a); b < prev(last, 2); ++b)
{
auto c = next(b);
auto d = prev(last);
while (c < d)
{
if (*a + *b + *c + *d < target) c++;
else if (*a + *b + *c + *d > target) d--;
else
{
result.push_back({ *a, *b, *c, *d });
++c;
--d;
}
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
1.2 优化
书上讲了几个优化的方法
1.2.1 利用map来缓存前两个的和####
unordered_map< int, vector< pair< int, int> > > cache;
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target)
{
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
unordered_map<int, vector<pair<int, int> > > cache;
for (size_t a = 0; a < num.size(); ++a)
{
for (size_t b = a + 1; b < num.size(); ++b)
{
cache[num[a] + num[b]].push_back(pair<int, int>(a, b));
}
}
for (int c = 0; c < num.size(); ++c)
{
for (size_t d = c + 1; d < num.size(); ++d)
{
const int key = target - num[c] - num[d];
if (cache.find(key) == cache.end()) continue;
const auto& vec = cache[key];
for (size_t k = 0; k < vec.size(); ++k)
{
if (c <= vec[k].second) continue;
result.push_back( { num[vec[k].first], num[vec[k].second], num[c], num[d] });
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
1.2.1 利用multi_map来缓存前两个的和####
用一个 hashmap 先缓存两个数的和,时间复杂度 O(n^2),空间复杂度 O(n^2)
// @author 龚陆安 (http://weibo.com/luangong)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& num, int target)
{
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
unordered_multimap<int, pair<int, int>> cache;
for (int i = 0; i + 1 < num.size(); ++i)
for (int j = i + 1; j < num.size(); ++j)
cache.insert(make_pair(num[i] + num[j], make_pair(i, j)));//!!!!!!!!!!!!!!!!!!!
for (auto i = cache.begin(); i != cache.end(); ++i)
{
int x = target - i->first;
auto range = cache.equal_range(x);
for (auto j = range.first; j != range.second; ++j)
{
auto a = i->second.first;
auto b = i->second.second;
auto c = j->second.first;
auto d = j->second.second;
if (a != c && a != d && b != c && b != d)
{
vector<int> vec = { num[a], num[b], num[c], num[d] };
sort(vec.begin(), vec.end());
result.push_back(vec);
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
