15. 三数之和 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

给定一个包含 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