LeetCode-15 三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0？请你找出所有和为 0 且不重复的三元组。

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

数据样例

示例 1：

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

1
2
输入：nums = []
输出：[]

示例 3：

1
2
输入：nums = [0]
输出：[]

提示：

  • $0 \leq nums.length \leq 3000$
  • $-10 ^ 5 \leq nums[i] \leq 10 ^ 5$

双指针 - $O(N ^ 2)$

两数之和

首先，我们可以回顾一下如何利用双指针算法求解两数之和：

两数之和：序列寻找 $a + b = 0$

  • 将序列进行排序为递增有序序列
  • 指针 $i$ 从序列 左侧 开始向右侧移动
  • 指针 $j$ 从序列 右侧 开始向左侧移动

双指针算法：

  • 当前如果 $nums[i] + nums[j] \geq 0$，则指针 $j$ 向左侧移动
  • 当前如果 $nums[i] + nums[j] < 0$，则指针 $i$ 向右侧移动

算法如下图所示：

  • $nums[i’] + nums[j’] > nums[i] + nums[j]$ 可以知道 $j$ 每次不需要从尾部开始重新枚举

三数之和

两数之和双指针算法理解后，三数之和就容易多了。

对于三数之和，我们可以固定一个值：

  • 枚举所有可能的 $a$ 的值

此时问题可以转换成：$b + c + a = 0$，其中 $a$ 是一个固定的值

那么这个问题就转换成了 两数之和

  • 分别用两个指针 $i, j$ 记录当前 $b, c$ 的值即可

不重复三元组

处理不重复三元组，只需要枚举过程中，如果 当前元素的值和前面的值相同（nums[i] == nums[i - 1]）则跳过，具体见代码注释。

时间复杂度 - $O(N ^ 2)$

  • 需要枚举一遍所有可能的 $a$：$O(N)$
  • 双指针求解两数之和 $b + c + a = 0$：$O(N)$

因此整体时间复杂度为 $O(N ^ 2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func threeSum(nums []int) [][]int {
    n := len(nums)      // 获取数组长度
    sort.Ints(nums)     // 将序列递增排序
    var res [][]int     // 记录答案
    for i := 0; i < n; i++ {    // 依次枚举 i，也就是枚举 a 的值
        if i > 0 && nums[i] == nums[i - 1] { continue } // 如果出现相同元素，则由于已经计算过了，跳过
        for j, k := i + 1, n - 1; j < k; j++ {  // 双指针 j, k 分别从序列左侧和右侧开始枚举，对应 b, c 的值。题目要求 i < j < k，因此 j 从 i + 1 开始枚举，同时 j < k 的时候停止
            if j > i + 1 && nums[j] == nums[j - 1] { continue } // 同样的，如果出现相同的元素，则跳过
            for j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0 { k-- }   // 观察下一个位置 k - 1，如果 nums[i] + nums[j] + nums[k - 1] >= 0，则 k 指针向左侧移动
            if nums[i] + nums[j] + nums[k] == 0 {   // 如果找到答案了，则记录下来
                res = append(res, []int{nums[i], nums[j], nums[k]})
            }
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1, k = n - 1; j < k; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) --k;
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return res;
    }
};