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 | class Solution {
public:
int moveForward(std::vector<int> &nums, int idx) {
while (idx + 1 < nums.size() && nums[idx] == nums[idx + 1])
idx++;
return idx + 1;
}
int moveBackward(std::vector<int> &nums, int idx) {
while (idx -1 >= 0 && nums[idx] == nums[idx - 1])
idx--;
return idx - 1;
}
void twoSum(std::vector<int> &nums, int fixed, vector<vector<int>> &ans) {
int left = fixed + 1;
int right = nums.size() - 1;
while(left < right) {
if (nums[left] + nums[right] == -nums[fixed]) {
ans.push_back({nums[fixed], nums[left], nums[right]});
left = moveForward(nums, left);
right = moveBackward(nums, right);
}
else if (nums[left] + nums[right] < -nums[fixed])
left = moveForward(nums, left);
else if (nums[left] + nums[right] > -nums[fixed])
right = moveBackward(nums, right);
}
}
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < nums.size(); i = moveForward(nums, i))
twoSum(nums, i, ans);
return ans;
}
};
|