-
Notifications
You must be signed in to change notification settings - Fork 0
/
triplets.cpp
61 lines (50 loc) · 1.76 KB
/
triplets.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
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
// Given an integer array nums, return all the triplets
// [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
// Notice that the solution set must not contain duplicate triplets.
class Solution
{
public:
using triplet = std::vector<int>;
using triplets = std::vector<triplet>;
triplets threeSum(std::vector<int> nums_copy)
{
triplets result;
if(nums_copy.size() == 1 || nums_copy.size() == 0)
return result;
std::sort(std::begin(nums_copy), std::end(nums_copy));
for(int i = 0; i < nums_copy.size() - 2; ++i)
{
if(i > 0 && nums_copy[i] == nums_copy[i - 1])
continue;
int left = i + 1;
int right = nums_copy.size() - 1;
while(left < right)
{
if(nums_copy[i] + nums_copy[left] + nums_copy[right] == 0)
{
triplet out = { nums_copy[i], nums_copy[left], nums_copy[right] };
while(left < right && nums_copy[left] == nums_copy[left + 1])
left++;
while(left < right && nums_copy[right] == nums_copy[right - 1])
right--;
result.emplace_back(std::move(out));
left++;
right--;
}
else if(nums_copy[i] + nums_copy[left] + nums_copy[right] < 0)
{
left++;
}
else
{
right--;
}
}
}
return result;
}
};