leetcode-15. 三数之和
滑动窗口
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
41class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int num1 = 0; num1 < nums.size() - 2; num1++)
{
if(num1 > 0 && nums[num1] == nums[num1 - 1])
continue; //去重
int num2 = num1 + 1;
int num3 = nums.size() - 1;
while (num2 < num3)
{
if(nums[num1] + nums[num2] + nums[num3] > 0)
{
num3--;
}
else if(nums[num1] + nums[num2] + nums[num3] < 0)
{
num2++;
}
else
{
vector<int> temp;
temp.push_back(nums[num1]);
temp.push_back(nums[num2]);
temp.push_back(nums[num3]);
result.push_back(temp);
while(num2 < num3 && nums[num2] == nums[num2 + 1])
num2++; //去重
while(num2 < num3 && nums[num3] == nums[num3 - 1])
num3--; //去重
num2++;
num3--;
}
}
}
return result;
}
};
哈希表
还有一种哈希的做法，但是去重会更加复杂，代码直接用别人的。
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
34class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[j], c = -(a + b)
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
continue;
}
unordered_set<int> set;
for (int j = i + 1; j < nums.size(); j++) {
if (j > i + 2
&& nums[j] == nums[j-1]
&& nums[j-1] == nums[j-2]) { // 三元组元素b去重
continue;
}
int c = 0 - (nums[i] + nums[j]);
if (set.find(c) != set.end()) {
result.push_back({nums[i], nums[j], c});
set.erase(c);// 三元组元素c去重
} else {
set.insert(nums[j]);
}
}
}
return result;
}
};