-
Notifications
You must be signed in to change notification settings - Fork 0
/
3sum.cpp
121 lines (121 loc) · 4.14 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
118
119
120
121
static const int __ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
return 0;
}();
class Solution {
public:
// vector<vector<int>> threeSum(vector<int>& nums) {
// int i,j,k;
// int n = nums.size();
// vector<int> arr;
// vector<vector<int>> result;
// sort(nums.begin(), nums.end());
// for(i=0; i<n; i++){
// if(nums[i]>0){
// break;
// }
// else
// {
// for(j=i+1; j<n; j++){
// for(k=j+1; k<n; k++){
// arr.clear();
// // if(i == j || j == k || i == k){
// // continue;
// // }
// if(nums[i] < 0 && nums[j] < 0 && nums[k] < 0){
// continue;
// }
// else{
// if((nums[i] + nums[j] + nums[k]) == 0){
// arr.push_back(nums[i]);
// arr.push_back(nums[j]);
// arr.push_back(nums[k]);
// sort(arr.begin(), arr.end());
// }
// else{
// continue;
// }
// }
// result.push_back(arr);
// }
// }
// }
// }
// n = result.size();
// for(i=0; i<n; i++){
// for(j=i+1;j<n; j++){
// if(result[i] == result[j]){
// result.erase(result.begin() + j);
// j--;
// n--;
// }
// else{
// continue;
// }
// }
// }
// sort(result.begin(), result.end());
// return result;
// // for(auto triplets : arr)
// // result.push_back(arr);
// // return result;
// }
vector<vector<int>> threeSum(vector<int> &nums) {
sort(nums.begin(), nums.end()); // Sorted Array
if (nums.size() < 3) { // Base case 1
return {};
}
if (nums[0] > 0) { // Base case 2
return {};
}
vector<vector<int>> answer;
for (int i = 0; i < nums.size();
++i) { // Traversing the array to fix the number.
if (nums[i] > 0) { // If number fixed is +ve, stop there because we can't
// make it zero by searching after it.
break;
}
if (i > 0 &&
nums[i] == nums[i - 1]) { // If number is getting repeated, ignore the
// lower loop and continue.
continue;
}
int low = i + 1,
high = nums.size() -
1; // Make two pointers high and low, and initialize sum as 0.
int sum = 0;
while (low < high) { // Search between two pointers, just similiar to
// binary search.
sum = nums[i] + nums[low] + nums[high];
if (sum > 0) { // If sum is +ve, means, we need more -ve numbers to make
// it 0, decreament high (high--).
high--;
} else if (sum < 0) { // If sum is -ve, means, we need more +ve numbers
// to make it 0, increament low (low++).
low++;
} else {
answer.push_back({nums[i], nums[low],
nums[high]}); // we have found the required triplet,
// push it in answer vector
int last_low_occurence = nums[low],
last_high_occurence =
nums[high]; // Now again, to avoid duplicate triplets, we have
// to navigate to last occurences of num[low] and
// num[high] respectively
while (low < high &&
nums[low] ==
last_low_occurence) { // Update the low and high with last
// occurences of low and high.
low++;
}
while (low < high && nums[high] == last_high_occurence) {
high--;
}
}
}
}
return answer;
}
};