「脸书」15 ～ 三数之和

基本信息

• 题号：15

• 题厂：脸书

• 难度系数：中

已知一个数组，数组元素可重复。随意从数组抽选 3 个元素，当三数之和为 0 时，此种组合需作为结果返回。返回结果无关顺序，但不能重复。如果没有三数之和满足 0，则返回空数组。

例如 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 组合元素重复一次，所以最后返回结果只有两组。

解题思路

本题为 leetcode 开山题 #1 两数之和（two sum）的变形升级题。「two sum」作为刷题届人人皆知的人身入门题，解题思路就是大一编程课上学习过的 「brute force 双重循环」。

#15 三数之和（three sum）升级后，解题思路还是沿袭「#1 two sum 二数之和」，将所有数进行三三组合一一比对，遇到满足和为 0 的情况时，将组合写入返回答案。

做「two sum 二数之和」时，采用双重 for 循环对照，做三数之和时，多添加一个元素，需要引入「双指针」技巧解题——第一个数字通过 for 循环遍历选出，剩下的两个数组通过「双指针」原理遍历查找。

基本解题思路确定后，还需要解决重复组合问题——此处引入「排序」方法进行解决。当数组排序后，进行 for 循环遍历时，只有当前数字和前一个数字不同时，我们才进行三数之和验证；否则直接跳过避免重复……

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 先将数组排序，解决重复问题。
        nums.sort()
        # 声明用于返回结果的空数组
        res = []
        
        # 一重循环选出第一个数字 v，为了后续「双指针」需求，同时记录 v 所对应的位置 i
        for i, v in enumerate(nums):
        # 排序后的数组，如果当前 v 和前一个数字相同，直接跳过（避免重复）
            if i > 0 and nums[i - 1] == v:
                continue
        # 当 v 不再与前一个数字重复时，还需要验证剩余的数组长度大于 2，才可进入「双指针」验证，否则个数不够，直接跳过……
            if i + 2 < len(nums):
                l, r = i + 1, len(nums) - 1
       
       # 一切条件满足后，按照「双指针」模板验证。⚠️ 注意，当找到满足三数之和的条件时，除了添加答案到返回值，还要波动左指针到下一个与当前 v 不同的位置，进行新一轮验证（否则会进入死循环） 
                while l < r:
                    curSum = nums[l] + nums[r] + v
                    if curSum == 0:
                        res.append([v, nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1

                    elif curSum < 0:
                        l += 1
                    else:
                        r -= 1

        return res

Constraints

• 3 <= nums.length <= 3000

• -105 <= nums[i] <= 105

做题前要和考官讨论数组最长最短长度。

• 数组最短为 3， 无需考虑数组小于 3 时的绝对无解特殊案例。

• 数组最长为 3000，暗示如果做 3 轮 brute force 循环，很可能因为效率太低无法通过。

测试

• n = 3 时，元素不同，相同，有满足和为 0 ，不为 0 的各种情况

• n = 3000 时，测试算法是否效率可行

• 当数组出现多个重复不间断元素时，测试代码能否过滤掉可能出现的重复答案

• ……

Big O

时间复杂度：O（n^2）

• 第一部分排序时，复杂度为 O（nlogn）。

• 第二部分，双指针循环为 O（n），乘以外部选第一个数字时的第一重循环 O（n），最终复杂度为 O（n^2）。

• 两次复杂度叠加后，取最高值，O（n^2）。

空间复杂度： O（n）

• 引入 res 数组记录答案

总结

• 题号靠前，同时又是开山第一题「#1 two sum 二数之和」的升级衍生题，非常有认真研究 + 定期复习之必要。

• 升级后，在数组基础上，杂糅了「双指针」，「排序」等常见基础知识点，重点考察对基础数据结构和算法的深度认知和灵活运用。

• 因为涉及多重循环和多个元素，本题特别讲究对 「edge case」的处理。想明白「双指针 + 排序」的解题思路后，对 「edge case」处理还需要特别细致方可避免数组越界等问题。