-
Notifications
You must be signed in to change notification settings - Fork 52
/
3Sum.cpp
34 lines (29 loc) · 984 Bytes
/
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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
int j = i + 1;
int k = nums.size() - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum < 0) {
j++;
} else if (sum > 0) {
k--;
} else {
result.push_back({nums[i], nums[j], nums[k]});
while ((j + 1) < nums.size() && nums[j] == nums[j+1]) j++;
j++;
while ((k - 1) >= 0 && nums[k] == nums[k - 1]) k--;
k--;
}
}
}
return result;
}
};