3 Sum

题目

https://leetcode.com/problems/3sum/description/

-w957

想法

可以说是很经典了。

最naive的方式,三层循环,遍历,O( n^3 ), 肯定不行

先排序,超过了就break,能省一点时间

唉,还有重复的问题呢,答案不能重复

哎呀,不想了,直接看答案吧,这种问题,肯定是那种知道解法之后,终身不忘的


O( N^2 )的解法:

排序
从左往右遍历,确定第一个数A[i]
对于第二个数和第三个数,分别是A[i + 1]和A[n - 1],一头一尾
如果相加为0,输出
如果大了,右边的往左走,否则,左边往右走

关于重复问题需要判断一下,需要判断一下,找到下一个不重复的

答案

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i + 2 < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int a = nums[i];
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
if (a + nums[l] + nums[r] < 0) {
l++;
} else if (a + nums[l] + nums[r] > 0) {
r--;
} else {
res.push_back({a, nums[l], nums[r]});
l++;
r--;
while (nums[l - 1] == nums[l])
l++;
while (nums[r + 1] == nums[r])
r--;
}
}
}
return res;
}
};

这里,重复的判断,就是遇到重复的,就继续向前走,直到不重复!