forked from fanfank/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
3sum.cpp
117 lines (115 loc) · 4.08 KB
/
3sum.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class Solution { //extremely ugly code, extremely ...
public:
vector<vector<int> > vv;
int binarySearchLow(vector<int> &a, int left, int right, int target) {
int lp = left;
while(left < right) {
int middle = left + (right - left) / 2;
if(a[middle] < target)
left = middle + 1;
else if(a[middle] > target)
right = middle - 1;
else
right = middle;
}
if(left > lp && a[left] > target)
return (left - 1);
return left;
}
int binarySearch(vector<int> &a, int left, int right, int target) {
while(left <= right) {
int middle = left + (right - left) / 2;
if(a[middle] == target)
return middle;
else if(a[middle] > target)
right = middle - 1;
else
left = middle + 1;
}
return -1;
}
vector<vector<int> > threeSum(vector<int> &num) {//an O(n^2) method
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vv.clear();
int sz = num.size();
if(sz < 3)
return vv;
sort(num.begin(), num.end());
int lp = binarySearchLow(num, 0, sz - 1, 0);
int rp = lp + 1, last = num[0] - 1;
for(; lp >= 0; --lp) {
if(rp - lp > 1 && num[lp] == num[lp+1])
continue;
last = num[0] - 1;
for(int j = rp; j < sz; ++j) {
if(last == num[j] || (lp + 1 != rp && num[j] == 0)) continue;
last = num[j];
int sum = num[lp] + num[j];
if(sum <= 0) {
if(-sum < num[j]) continue;
int pos = binarySearch(num, j + 1, sz - 1, -sum);
if(pos != -1) {
vv.push_back(vector<int>({num[lp], num[j], num[pos]}));
}
} else {
if(-sum > num[lp]) continue;
int pos = binarySearch(num, 0, lp - 1, -sum);
if(pos != -1) {
vv.push_back(vector<int>({num[pos], num[lp], num[j]}));
}
}
}
}
return vv;
}
};
/**********************************************************
a better way to solve this problem, to solve K SUM problem
**********************************************************/
class Solution { //better and extensible code
public:
vector<vector<int> > vv;
int binarySearch(vector<int> &a, int left, int right, int target) {
while(left <= right) {
int middle = left + (right - left) / 2;
if(a[middle] == target)
return middle;
else if(a[middle] < target)
left = middle + 1;
else
right = middle - 1;
}
return -1;
}
void kSum(vector<int> &a, int target, int k, int index, vector<int> &helper) {
int sz = a.size();
if(k > sz - index)
return;
if(k == 1) {
int pos = binarySearch(a, index, sz - 1, target);
if(pos != -1) {
helper.push_back(a[pos]);
vv.push_back(helper);
helper.pop_back();
}
return;
}
for(int i = index; i <= sz - k; ++i) {
if(i != index && a[i] == a[i-1])
continue;
helper.push_back(a[i]);
kSum(a, target - a[i], k - 1, i + 1, helper);
helper.pop_back();
}
}
vector<vector<int> > threeSum(vector<int> &num) {//an O(n^2) method
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vv.clear();
sort(num.begin(), num.end());
vector<int> tmp;
kSum(num, 0, 3, 0, tmp);
return vv;
}
};