题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 01】，包含本题的基本思路，以及两个优化。制作不易，欢迎点赞关注~

思路

为方便双指针以及跳过相同元素，先把 $\mathit{\text{nums}}$ 排序。

枚举 $\mathit{\text{nums}}[i]$，问题变成 $\mathit{\text{nums}}[j]+\mathit{\text{nums}}[k]=-\mathit{\text{nums}}[i]$，这和 167. 两数之和 II - 输入有序数组 是一样的。

题目要求答案中不能有重复的三元组。如何避免重复？

在外层循环中，如果发现 $\mathit{\text{nums}}[i]=\mathit{\text{nums}}[i-1]$，那么 $\mathit{\text{nums}}[i]$ 与后面两个数组成的和为 $0$ 的三元组，$\mathit{\text{nums}}[i-1]$ 也能组成一模一样的三元组，这就重复了，所以遇到 $\mathit{\text{nums}}[i]=\mathit{\text{nums}}[i-1]$ 的情况，直接 $\mathtt{\text{continue}}$。

在内层循环中，当三数之和等于 $0$ 时，为避免把相同的三元组计入答案，跳过后续相同的 $\mathit{\text{nums}}[j]$ 和 $\mathit{\text{nums}}[k]$（也可以只跳过相同的 $\mathit{\text{nums}}[j]$）。

优化

优化一：如果 $\mathit{\text{nums}}[i]$ 与后面最小的两个数相加 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[i+1]+\mathit{\text{nums}}[i+2]>0$，那么后面不可能存在三数之和等于 $0$，$\mathtt{\text{break}}$ 外层循环。

优化二：如果 $\mathit{\text{nums}}[i]$ 与后面最大的两个数相加 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[n-2]+\mathit{\text{nums}}[n-1]<0$，那么内层循环不可能存在三数之和等于 $0$，但继续枚举，$\mathit{\text{nums}}[i]$ 可以变大，所以后面还有机会找到三数之和等于 $0$，$\mathtt{\text{continue}}$ 外层循环。

写法一

Python 解法1

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n - 2):
            x = nums[i]
            if i > 0 and x == nums[i - 1]:  # 跳过重复数字
                continue
            if x + nums[i + 1] + nums[i + 2] > 0:  # 优化一
                break
            if x + nums[-2] + nums[-1] < 0:  # 优化二
                continue
            j = i + 1
            k = n - 1
            while j < k:
                s = x + nums[j] + nums[k]
                if s > 0:
                    k -= 1
                elif s < 0:
                    j += 1
                else:  # 三数之和为 0
                    ans.append([x, nums[j], nums[k]])
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:  # 跳过重复数字
                        j += 1
                    k -= 1
                    while k > j and nums[k] == nums[k + 1]:  # 跳过重复数字
                        k -= 1
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i && x == nums[i - 1]) continue; // 跳过重复数字
            if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                } else if (s < 0) {
                    j++;
                } else { // 三数之和为 0
                    ans.push_back({x, nums[j], nums[k]});
                    for (j++; j < k && nums[j] == nums[j - 1]; j++); // 跳过重复数字
                    for (k--; k > j && nums[k] == nums[k + 1]; k--); // 跳过重复数字
                }
            }
        }
        return ans;
    }
};

写法二

上面跳过重复数字的循环，也可以这样写：如果 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j]+\mathit{\text{nums}}[k]=0$，并且 $j>i+1$ 且 $\mathit{\text{nums}}[j]=\mathit{\text{nums}}[j-1]$，则说明我们在之前找到了一样的三元组。

比如 $\mathit{\text{nums}}=[-3,1,1,2,2]$，首先我们找到 $\mathit{\text{nums}}[0]+\mathit{\text{nums}}[1]+\mathit{\text{nums}}[4]=0$，在 $j$ 加一，$k$ 减一后，发现 $\mathit{\text{nums}}[0]+\mathit{\text{nums}}[2]+\mathit{\text{nums}}[3]$ 也等于 $0$，但 $\mathit{\text{nums}}[2]=\mathit{\text{nums}}[1]$（这同时说明 $\mathit{\text{nums}}[3]=\mathit{\text{nums}}[4]$），是重复的三元组，不能加入答案。

Python 解法3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n - 2):
            x = nums[i]
            if i > 0 and x == nums[i - 1]:  # 跳过重复数字
                continue
            if x + nums[i + 1] + nums[i + 2] > 0:  # 优化一
                break
            if x + nums[-2] + nums[-1] < 0:  # 优化二
                continue
            j = i + 1
            k = n - 1
            while j < k:
                s = x + nums[j] + nums[k]
                if s > 0:
                    k -= 1
                elif s < 0:
                    j += 1
                else:  # 三数之和为 0
                    # j = i+1 表示刚开始双指针，此时 j 左边没有数字
                    # nums[j] != nums[j-1] 说明与上一轮循环的三元组不同
                    if j == i + 1 or nums[j] != nums[j - 1]:
                        ans.append([x, nums[j], nums[k]])
                    j += 1
                    k -= 1
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i && x == nums[i - 1]) continue; // 跳过重复数字
            if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                } else if (s < 0) {
                    j++;
                } else { // 三数之和为 0
                    // j = i+1 表示刚开始双指针，此时 j 左边没有数字
                    // nums[j] != nums[j-1] 说明与上一轮循环的三元组不同
                    if (j == i + 1 || nums[j] != nums[j - 1]) {
                        ans.push_back({x, nums[j], nums[k]});
                    }
                    j++;
                    k--;
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。排序 $\mathcal{O}(n\log n)$。外层循环枚举第一个数，就变成 167. 两数之和 II - 输入有序数组 了，做法是 $\mathcal{O}(n)$ 双指针。所以总的时间复杂度为 $\mathcal{O}(n^2)$。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。忽略排序的栈开销。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府