【面试经典150 | 双指针】三数之和

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【双指针】【数组】

---

题目来源

面试经典150 | 15. 三数之和

---

题目解读

给你一个整数数组 nums，找出其中所有同时满足以下条件的三元组：

• nums[i] + nums[j] + nums[k] = 0；
• i != j、j != k 且 k != i

注意：答案中不允许包含重复的三元组。

---

解题思路

方法一：暴力枚举

找出和为 0 的三元组，最容易想到的方法就是枚举所有可能的三元组，然后求和。但是答案中不允许包含重复的三元组，因此想到先进行排序处理，将数组 nums 中所有重复的元素放在一起，方便后续的去重处理，这一步也是后续几种方法的必要的步骤。

枚举所有可能的三元组的方法最容易想到，但是时间复杂度为 $O(n^3)$，$n$ 为数组 nums 的长度，本题的数据量达到 $10^3$，必然超时。

方法二：双指针

为了应对重复答案的情况出现，我们首先对数组 nums 进行排序处理。

接着，枚举第一个加数 nums[i]，剩下两个加数的查找我们可以使用 两数之和 中双指针的思想来解决，具体地：

• 枚举第一个加数 nums[i]：
• 如果 i >= 1 且 nums[i] = nums[i-1]，说明数字 nums[i] 已经作为第一个元素了， 我们需要则继续枚举下一个位置的 nums[i] 作为第一个加数；
• 否则，利用双指针查找第二、三个加数：
• 维护双指针 j、k 分别指向需要查找的第二、三个数字位置，初始化 j = i + 1、k = n - 1；
• 如果 nums[i] + nums[j] + nums[k] > 0，则 --k；
• 如果 nums[i] + nums[j] + nums[k] < 0，则 ++j；
• 如果 nums[i] + nums[j] + nums[k] = 0，则当前的 {nums[i], nums[j], nums[k]} 为一个满足条件的三元组并加入到 答案数组 ret 中，并且右移 j 到下一个与数字 nums[j] 的位置，左移 k 到下一个与数字 nums[k] 的位置 。

最后，返回答案数组 ret。

优化

本题中还有一些可以优化的地方：

• 如果 n < 3，即数组的长度小于 3，不会有三个数；
• 如果排序后的 nums[0] > 0，表明数组中的所有数字都大于 0，一定不会有和为 0 的三元组；
• 如果排序后的 nums[n-1] > 0，表明数组中的所有数字都小于 0，一定不会有和为 0 的三元组；

加上以上的优化代码，双指针解法就是最优的解法了。

实现代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());

        if(n < 3 || nums[0] > 0 || nums[n-1] < 0){
            return ret;
        }
        int i, j, k;
        for(i = 0; i < n-2; ++i){
            if(i && nums[i] == nums[i-1]){
                continue;
            }
            j = i + 1;
            k = n - 1;
            while(j < k){
                int target = nums[i] + nums[j] + nums[k];
                if(target > 0){
                    --k;
                }
                else if(target < 0){
                    ++j;
                }
                else{
                    ret.push_back({nums[i], nums[j], nums[k]});
                    ++j;
                    --k;
                    while(j < k && nums[j] == nums[j-1]) ++j;
                    while(j < k && nums[k] == nums[k + 1]) --k;
                }
            }

        }
        return ret;
    }
};
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

复杂度分析

时间复杂度：$O(n^2)$，$n$ 为数组 nums 的长度，枚举第一个加数的时间复杂度为 $O(n)$，利用双指针查找满足条件的第二、三个加数的时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(n^2)$。

空间复杂度：$O(logn)$，双指针解法仅使用有限个额外空间，排序占用的额外空间为 $O(logn)$，因此空间复杂度为 $O(logn)$。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。