Find All Four Sum Numbers
Given an array of integers and another number. Find all the unique quadruple from the given array that sums up to the given number.
- Time : O(n^3)
- Space : O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
vector<vector<int>> fourSum(vector<int> &arr, int k) {
vector<vector<int>> res;
sort(begin(arr), end(arr));
int n = arr.size();
for(int i = 0; i < n; i++) {
if(i and arr[i] == arr[i-1]) continue;
for(int j = i + 1; j < n; j++) {
if(j != i + 1 and arr[j] == arr[j-1]) continue;
int l = j + 1, r = n - 1;
int target = k - arr[i] - arr[j];
while(l < r) {
int sum = arr[l] + arr[r];
if(sum == target) {
res.push_back({arr[i], arr[j], arr[l], arr[r]});
l++, r--;
while(l < r and arr[l] == arr[l-1]) l++;
while(l < r and arr[r] == arr[r+1]) r--;
} else if(sum > target) {
r--;
} else {
l++;
}
}
}
}
return res;
}
};
|
- Time : O(n^2)
- Space : O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public:
vector<vector<int>> fourSum(vector<int> &arr, int k) {
vector<vector<int>> res;
sort(begin(arr), end(arr));
unordered_map<int, vector<vector<int>>> mp;
unordered_map<int, int> counter;
int n = arr.size();
for(int i = 0; i < n; i++) {
counter[arr[i]]++;
if(i and arr[i] == arr[i-1]) continue;
for(int j = i + 1; j < n; j++) {
if(j > i + 1 and arr[j] == arr[j-1]) continue;
mp[arr[i] + arr[j]].push_back({arr[i], arr[j]});
}
}
unordered_set<string> vis;
for(auto& p : mp) {
int sum = p.first;
auto vec = p.second;
int target = k - sum;
if(target >= sum) continue;
if(mp.count(target)) {
auto vec2 = mp[target];
for(int i = 0; i < vec.size(); i++) {
for(int j = 0; j < vec2.size(); j++) {
int a = vec[i][0], b = vec[i][1], c = vec2[j][0], d = vec2[j][1];
bool insert = true;
unordered_map<int, int> subCounter;
subCounter[a]++;
subCounter[b]++;
subCounter[c]++;
subCounter[d]++;
for(auto& sub : subCounter) {
if(counter[sub.first] < sub.second) insert = false;
if(!insert) break;
}
if(!insert) continue;
vector<int> ans {a,b,c,d};
sort(begin(ans), end(ans));
string hash = "";
for(int n : ans)
hash += to_string(n) + '#';
if(!vis.count(hash)) {
vis.insert(hash);
res.push_back(ans);
}
}
}
}
}
sort(begin(res),end(res));
return res;
}
};
|
