15. 三数之和 - 力扣(LeetCode)

题目描述

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

题解

最先萌发的肯定是暴力求解的方法,试探每一种可能性。三重循环,时间复杂度比较高,是[latex] O(n^3) [/latex]。

代码

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

执行结果

超出时间限制!!

优化

借鉴之前两数之和的思路,用空间来换时间,用哈希表存储前两个数的信息。通过一个数来找另两个数满足三数之和为00。

代码

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>res;
vector<int>temp;
map<int,vector<int>>myMap;
sort(nums.begin(), nums.end());//排序一下 是为了去重,但并没有达到想要的效果
int num;
int len = nums.size();
for(int i = 0; i < len - 1; ++i){
if(i > 0 && nums[i - 1] == nums[i]){
continue;
}
for(int j = i + 1; j < len; ++j){
if(j > i + 1 && nums[j - 1] == nums[j]){
continue;
}
if(myMap.find(nums[j]) != myMap.end()){//存在于map中,则视为符合题意的解
temp.clear();
temp.push_back(nums[j]);
temp.push_back(myMap[nums[j]][0]);
temp.push_back(myMap[nums[j]][1]);
res.push_back(temp);
}
else{//不存在,就在map中记录下信息
temp.clear();
num = 0 - nums[i] - nums[j];
temp.push_back(nums[i]);
temp.push_back(nums[j]);
myMap[num] = temp;
}
}
}
return res;
}
};
//该解未能有效去重,不能AC,只是提出一种思路。

再优化

为了便于去重,首先仍是排序,复杂度为[latex] nlog_{2}n [/latex]。然后用双指针的方法,初始化指向数据的首尾,中间数b,保持不动。判断a+b+c。若a+b+c > 0则需减小,尾指针向左移动;若a+b+c < 0则需增大,头指针向右移动。将有某个指针指向b时,则结束。调整b,继续上次操作。

代码

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>res;
sort(nums.begin(), nums.end());
int len = nums.size(), beg, end, cnt;
for(int i = 1; i < len - 1; ++i){
while(beg < i && end > i){//位于i两侧
if(nums[beg] +nums[i] + nums[end] > 0){//偏大,减小
--end;
}
else if(nums[beg] + nums[i] + nums[end] < 0){//偏小,增大
++beg;
}
else{//刚好,同时移动
int a[3] = {nums[beg], nums[i], nums[end]};
vector<int>tmp(a, a + 3);
res.push_back(tmp);
while(beg < i && nums[beg + 1] == nums[beg]) ++beg;//去重
while(end > i && nums[end - 1] == nums[end]) --end;//去重
++beg;
--end;
}
}
}
return res;
}
}
//未AC,去重太麻烦了,针对[0, 0, 0, 0]有问题。

再再优化

换个思路,考虑排序后,固定a,两指针分别指向b和c,判断方式仍然相同,当然可以有更多优化,比如a>0时,a+b+c一定大于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
31
32
33
34
35
36
37
38
39
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>res;
sort(nums.begin(), nums.end());
int len = nums.size(), beg, end, sum;
for(int i = 0; i < len - 1; ++i){
if(nums[i] > 0){
break;
}
if(i > 0 && nums[i] == nums[i - 1]){//去重
continue;
}
beg = i + 1, end = len -1;
while(beg < end){
int sum = nums[i] + nums[beg] + nums[end];
if(sum > 0){
--end;
}
else if(sum < 0){
++beg;
}
else{
res.push_back({nums[i], nums[beg], nums[end]});
while(beg < end && nums[beg] == nums[beg + 1]){//去重
++beg;
}
while(beg < end && nums[end] == nums[end - 1]){//去重
--end;
}
++beg;
--end;
}
}
}
return res;
}
};
//AC