题目：
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]
]
题解：
这个题与3Sum类似，求4Sum就在原基础上再加上一层循环就可以了。这里只给出此种解法思路的其中一个解法。
Solution 1 (36ms)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> sv;
sort(nums.begin(), nums.end());
int n = nums.size(); for(int i=; i<n-; i++) {
for(int j=i+; j<n-; j++) {
int k = j+, l = n-;
int a = nums[i], b = nums[j];
while(k<l) {
int c = nums[k], d = nums[l];
if(a+b+c+d == target) {
sv.insert({a,b,c,d});
k++;
l--;
}
else if(a+b+c+d < target) k++;
else l--;
}
}
}
return vector<vector<int>> (sv.begin(),sv.end());
}
};
还有一种解法，也是利用了3Sum，不过不是再加一层循环，而是直接调用3Sum函数：取nums[i]，然后对后续剩余数组元素求3Sum，tar为target – nums[i]；
Solution 2 (32ms)
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &nums, int target) {
set<vector<int>> sv;
sort(nums.begin(), nums.end());
int n = nums.size(); for(int i=; i<n-; i++) {
int a = nums[i];
int j = i+, k = n-;
while(j<k) {
int b = nums[j], c = nums[k];
if(a+b+c == target) {
sv.insert({a,b,c});
j++;
k--;
}
else if(a+b+c > target) k--;
else j++;
}
}
return vector<vector<int>> (sv.begin(),sv.end());
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> vv;
sort(nums.begin(), nums.end());
int n = nums.size(); for(int i=; i<n-; i++) {
if(i> && nums[i] == nums[i-]) continue;
//截取剩余数组
vector<int> v(nums.begin()+i+,nums.end());
vector<vector<int>> tmp = threeSum(v, target - nums[i]);
for(int j=; j<tmp.size(); j++) {
tmp[j].insert(tmp[j].begin(), nums[i]);
vv.push_back(tmp[j]);
}
}
return vv;
}
};
还有一种更为优化的解法，思路是一致的，只是加了一个小技巧：在两个外循环中先判断四个值的和与target的大小，即
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
通过这两条语句减少了搜索时间，不必进入内循环判断；对于j同理。
Solution 3 (12ms)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> sv;
sort(nums.begin(), nums.end());
int n = nums.size();
if(n<) return vector<vector<int>> (sv.begin(),sv.end());
for(int i=; i<n-; i++) {
if(nums[i]+nums[i+]+nums[i+]+nums[i+]>target) break;
if(nums[i]+nums[n-]+nums[n-]+nums[n-]<target) continue;
if(i>&&nums[i]==nums[i-]) continue;
for(int j=i+; j<n-; j++) {
if(j>i+&&nums[j]==nums[j-]) continue;
if(nums[i]+nums[j]+nums[j+]+nums[j+]>target) break;
if(nums[i]+nums[j]+nums[n-]+nums[n-]<target) continue;
int k = j+, l = n-;
int a = nums[i], b = nums[j];
while(k<l) {
int c = nums[k], d = nums[l];
if(a+b+c+d == target) {
sv.insert({a,b,c,d});
k++;
l--;
}
else if(a+b+c+d < target) k++;
else l--;
}
}
}
return vector<vector<int>> (sv.begin(),sv.end());
}
};
Solution 4
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i = ; i < n - ; ++i){
for(int j = i + ; j < n - ; ++j){
int begin = j + , end = n - ;
while(begin < end){
int sum = nums[i] + nums[j] + nums[begin] + nums[end];
if(sum == target)
res.push_back({nums[i], nums[j], nums[begin++], nums[end--]});
else if (sum < target)
++begin;
else
--end;
}
}
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
};
去重的另一种方法， 使用了algorithm
Solution 5
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> res;
sort(nums.begin(), nums.end());
unordered_multimap<int, pair<int, int>> map;
for(int i = ; i < n - ; ++i){
for(int j = i + ; j < n; ++j){
map.insert(make_pair(nums[i] + nums[j], make_pair(i, j)));
}
}
for(auto i = map.begin(); i != map.end(); ++i){
int val = target - i->first;
auto range = map.equal_range(val);
for(auto j = range.first; j != range.second; ++j){
auto a = i->second.first, b = i->second.second;
auto c = j->second.first, d = j->second.second;
if(a != c && a != d && b != c && b != d){
vector<int> tmp = {nums[a], nums[b], nums[c], nums[d]};
sort(tmp.begin(), tmp.end());
res.push_back(tmp);
}
}
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
};
先缓存两个数的和，注意要使用multimap（from 九章算法）
