Leetcode 剑指 Offer II 007. 数组中和为 0 的三个数

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

• 输入：nums = [-1,0,1,2,-1,-4]
• 输出：[[-1,-1,2],[-1,0,1]]
• 解释：
  • nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
  • nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
  • nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
  • 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
  • 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

• 输入：nums = [0,1,1]
• 输出：[]
• 解释：唯一可能的三元组和不为 0 。

示例 3：

• 输入：nums = [0,0,0]
• 输出：[[0,0,0]]
• 解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

题目思考

1. 如何尽可能优化时间复杂度?

解决方案

思路

• 分析题目, 最容易想到的做法就是暴力三重循环+集合去重: 遍历所有三个数字的组合, 找出和为 0 的, 再利用集合去重
• 但这种做法时间效率太低 (O(N^3)), 如何优化呢?
• 回顾上周的题目: Leetcode 剑指 Offer II 006. 排序数组中两个数字之和, 我们最终用 O(N) 的时间复杂度解决了『有序数组』两数之和为 target 的问题
• 对这个问题来说, 如果我们先对数组排序, 然后固定第一个数字 a, 求剩下两个数的和为 -a 的组合, 是不是就能直接转换成那个问题了?
• 这样时间复杂度就可以降低为 O(N^2) (排序预处理是 O(NlogN), 外层循环 a 需要 O(N), 内层求两数和也需要 O(N))
• 具体双指针求和的思考过程大家可以参考上周的题解, 这里就不再赘述了
• 不过这个问题多了去重的要求, 由于我们已经对数组进行了排序, 所以只需要比较相邻的数字, 具体做法如下:
  1. 针对第一个数字 a, 我们如果遇到多个连续相同的 a, 那么只有第一次才处理, 后面的直接跳过即可
  2. 针对后面两个数字 b 和 c, 我们找到一个满足条件的组合后, 先跟结果列表的最后一个组合比较, 如果两者相同, 说明是重复, 也跳过
• 这还没完, 得益于数组的排序, 我们还可以进一步优化时间:
  1. 如果当前的 a 加上它后面紧挨着的两个数字已经超过 0, 就没必要继续遍历第一个数字大于等于 a 的任何其他组合了, 因为它们的和只会更大, 也即 break 外层循环
  2. 如果当前的 a 加上数组末尾的两个数字仍小于 0, 则没必要继续固定当前的 a 遍历 b 和 c 了, 因为它们的和只会更小, 也即 continue 外层循环
• 下面代码中对上述每个步骤都有详细注释, 方便大家理解

复杂度

• 时间复杂度 O(N^2): 排序 O(NlogN), 两重循环 O(N^2)
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 排序+三指针+两去重+两剪枝
        res = []
        # 先对数组进行排序, 从而可以使用j和k双指针求和
        nums.sort()
        n = len(nums)
        for i in range(n - 2):
            a = nums[i]
            if i > 0 and a == nums[i - 1]:
                # 去重1: 当前的a已经处理过了, 避免重复处理
                continue
            if a + nums[i + 1] + nums[i + 2] > 0:
                # 剪枝1: 相邻的三个数字之和已经大于0了, 后续更大于0, 直接break
                break
            if a + nums[-1] + nums[-2] < 0:
                # 剪枝2: 当前数字和最后两个数字之和仍小于0, 中间部分肯定更小于0, 继续遍历下一个i
                continue
            j, k = i + 1, n - 1
            while j < k:
                b, c = nums[j], nums[k]
                sm = a + b + c
                if sm == 0:
                    # 三数之和恰好等于0, 找到一个有效组合
                    # 左右指针同时向中间移动, 不再使用它们
                    i += 1
                    k -= 1
                    if res and res[-1] == [a, b, c]:
                        # 去重2: [a,b,c]组合已经添加到最终结果, 避免重复处理
                        # 注意由于数组有序, 所以已经存在的[a,b,c]一定是res列表的最后一个元素
                        continue
                    res.append([a, b, c])
                elif sm < 0:
                    # 三数之和小于0, 左指针右移
                    j += 1
                else:
                    # 三数之和大于0, 右指针右移
                    k -= 1
        return res

大家可以在下面这些地方找到我~????

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~????

最后

以上就是明亮雪糕为你收集整理的Leetcode 剑指 Offer II 007. 数组中和为 0 的三个数的全部内容，希望文章能够帮你解决Leetcode 剑指 Offer II 007. 数组中和为 0 的三个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。