# [leetcode] 4sum

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, abcd)
• 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> &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.

```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);
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;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.