forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
4sum.cpp
79 lines (75 loc) · 2.52 KB
/
4sum.cpp
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Time: O(n^3)
// Space: O(1)
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
int len = num.size();
int left, right, sum;
sort(num.begin(), num.end());
vector<vector<int>> res;
for (int i = 0; i < len - 3; ++i) {
if (i && num[i] == num[i - 1]) {
continue;
}
for (int j = i + 1; j < len - 2; ++j) {
if (j != i + 1 && num[j] == num[j - 1]) {
continue;
}
sum = target - num[i] - num[j];
left = j + 1, right = len - 1;
while (left < right) {
if (num[left] + num[right] == sum) {
res.push_back({num[i], num[j], num[left], num[right]});
++left, --right;
while (left < right && num[left] == num[left - 1]) {
++left;
}
while (left < right && num[right] == num[right + 1]) {
--right;
}
} else {
if (num[left] + num[right] > sum) {
--right;
} else {
++left;
}
}
}
}
}
return res;
}
};
// Time: O(n^4)
// Space: O(n^2)
class Solution2 {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int>> ans;
if (num.size() < 4) {
return ans;
}
sort(num.begin(), num.end());
unordered_multimap<int, pair<int, int>> cache;
for (int i = 0; i < num.size(); ++i) {
for (int j = i + 1; j < num.size(); ++j) {
cache.emplace(num[i] + num[j], make_pair(i, j));
}
}
for (auto i = cache.begin(); i != cache.end(); ++i) {
auto a = i->second.first;
auto b = i->second.second;
auto range = cache.equal_range(target - i->first);
for (auto j = range.first; j != range.second; ++j) {
auto c = j->second.first;
auto d = j->second.second;
if (b < c) {
ans.push_back({num[a], num[b], num[c], num[d]});
}
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
return ans;
}
};