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)
所有的Ksum问题都可以通过枚举一个元素，退化成K-1sum，k-2sum…最终变成2sum，然后用2sum的双指针算法（头指针，尾指针）在线性时间解决，也就是Ksum问题有一个o(n^(k-1))的通解。
版本一：o(n^3)
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int>> re;
if(num.size() < 4){
return re;
}
sort(num.begin(), num.end());
for(int i = 0; i < num.size() - 3; ){
for(int j = i + 1; j < num.size() - 2; ){
int a = num[i];
int b = num[j];
int thisTarget = target - a - b;
int k = j + 1;
int l = num.size() - 1;
while(k < l){
int sum = num[k] + num[l];
if(sum == thisTarget){
vector<int> thisRe;
thisRe.push_back(a);
thisRe.push_back(b);
thisRe.push_back(num[k]);
thisRe.push_back(num[l]);
re.push_back(thisRe);
k++;
while(k < l && num[k] == num[k - 1]){
k++;
}
l--;
while(l > k && num[l] == num[l + 1]){
l--;
}
}
else if(sum > thisTarget){
l--;
while(l > k && num[l] == num[l + 1]){
l--;
}
}
else{
k++;
while(k < l && num[k] == num[k - 1]){
k++;
}
}
}
j++;
while(j < num.size() && num[j] == num[j - 1]){
j++;
}
}
i++;
while(i < num.size() && num[i] == num[i - 1]){
i++;
}
}
return re;
}
};
AC.
尝试用空间换时间，加入hashtable，key为每个2-pair的sum，value为一个vector，储存所有和为sum的id-pair。复杂度o(n^2*k)，k为建哈希表和查哈希表的复杂度，与数据和哈希表的结构有关。但是却超时。
版本二：o(n^2*k) 超时，好奇怪，求高人指点。
class Solution {
public:
unordered_map<int, vector<vector<int>>> hashTable;
vector<vector<int>> re;
vector<vector<int>> fourSum(vector<int> &num, int target) {
if(num.size() < 4){
return re;
}
sort(num.begin(), num.end());
//build hashmap
for(unsigned int i = 0; i < num.size(); ){
for(unsigned int j = i + 1; j < num.size(); ){
int sum = num[i] + num[j];
vector<int> thisPair;
thisPair.push_back(i);
thisPair.push_back(j);
if(hashTable.find(sum) == hashTable.end()){//not found
vector<vector<int>> pairs;
pairs.push_back(thisPair);
hashTable[sum] = pairs;
}
else{//found
hashTable[sum].push_back(thisPair);
}
j++;
while(j < num.size() && num[j] == num[j - 1]){
j++;
}
}
i++;
while(i < num.size() && num[i] == num[i - 1]){
i++;
}
}
//search hashmap
for(unsigned int i = 0; i < num.size(); ){
for(unsigned int j = i + 1; j < num.size(); ){
int a = num[i];
int b = num[j];
int thisTarget = target - a - b;
if(hashTable.find(thisTarget) != hashTable.end()){//found
vector<vector<int>> pairs = hashTable[thisTarget];
for(unsigned int k = 0; k < pairs.size(); k++){
int idx = pairs[k][0];
int idy = pairs[k][1];
if(idx > j){//not duplicated
vector<int> thisRe;
thisRe.push_back(a);
thisRe.push_back(b);
thisRe.push_back(num[idx]);
thisRe.push_back(num[idy]);
re.push_back(thisRe);
}
}
}
j++;
while(j < num.size() && num[j] == num[j - 1]){
j++;
}
}
i++;
while(i < num.size() && num[i] == num[i - 1]){
i++;
}
}
return re;
}
};