-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path7.threeSum.cpp
More file actions
executable file
·92 lines (82 loc) · 2.15 KB
/
Copy path7.threeSum.cpp
File metadata and controls
executable file
·92 lines (82 loc) · 2.15 KB
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
/*
@filename 7.cpp
@author caonan
@date 2022-03-17 15:14:28
@reference 剑指offer专项
@url https://leetcode-cn.com/problems/1fGaJU/
@brief 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0
且 不重复 的三元组。
*/
#include <assert.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
int length = nums.size();
if (length < 3) {
return ret;
}
std::sort(nums.begin(), nums.end());
int i = 0;
while (i < length - 2) {
addTwoSum(i, nums, ret);
int tmp = nums[i];
while (tmp == nums[i] && i < length - 2) {
i++;
}
}
return ret;
}
private:
void addTwoSum(int i, vector<int>& nums, vector<vector<int>>& ret)
{
int j = i + 1;
int k = nums.size() - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] == 0) {
ret.push_back(vector<int>{nums[i], nums[j], nums[k]});
int tmp = nums[j];
while (tmp == nums[j] && j < k) {
j++;
}
} else if (nums[i] + nums[j] + nums[k] > 0) {
k--;
} else {
j++;
}
}
}
};
void print_vec(const vector<vector<int>>& arrs)
{
for (auto& v : arrs) {
for (auto& vv : v) {
printf("%d ", vv);
}
printf("\n");
}
}
int main()
{
Solution s;
vector<int> nums{-1, 0, 1, 2, -1, -4};
vector<vector<int>> ret{{-1, -1, 2}, {-1, 0, 1}};
// auto tmp = s.threeSum(nums);
// print_vec(tmp);
assert(s.threeSum(nums) == ret);
vector<vector<int>> ret1;
vector<int> nums1{};
assert(s.threeSum(nums1) == ret1);
vector<vector<int>> ret2{{0, 0, 0}};
vector<int> nums2{0, 0, 0, 0};
assert(s.threeSum(nums2) == ret2);
return 0;
}