「脸书」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」处理还需要特别细致方可避免数组越界等问题。
喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!
![](https://imagedelivery.net/kDRCweMmqLnTPNlbum-pYA/prod/avatar/035b7f52-7322-46ce-8460-11dc008d59fb.jpeg/public)
![](https://imagedelivery.net/kDRCweMmqLnTPNlbum-pYA/prod/avatar/035b7f52-7322-46ce-8460-11dc008d59fb.jpeg/public)