题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
-
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
-
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 1:
- 输入:
- big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
- small = [1,5,9]
- 输出: [7,10]
示例 2:
- 输入:
- big = [1,2,3]
- small = [4]
- 输出: []
提示：
- big.length <= 100000
- 1 <= small.length <= 100000
题目思考
- 如何快速找到包含关系?
解决方案
思路
- 分析题目, 一个很容易想到的方案就是暴力两重循环:
- 外层循环 big 的每个下标作为起点
- 内层将 small 转成集合, 然后从 big 起点开始, 如果数字在集合中则将其移除, 直到集合为空
- 此时就找到了一个有效子数组, 根据其长度更新最终最短子数组即可
- 但上述方案复杂度是 O(N^2), 根据题目数据规模肯定会超时, 如何优化效率呢?
- 包含问题一般可以采用滑动窗口的思路, 这道题也不例外, 只是需要一些额外的数据结构
- 我们可以将 small 转成{val:cnt}的计数字典, 同时维护一个尚未匹配的数字个数 unmatch, 用于加速判断窗口的有效性
- 然后开始遍历右边界, 当遇到 small 内的元素时, 就将其计数减 1
- 另外在首次遇到 small 内的元素时, 就将 unmatch 减 1, 表示当前数字在这个窗口内得到了匹配
- 当 unmatch 变成 0 时, 就说明当前窗口包含了 small 的所有元素, 接下来开始将左边界向右移, 目的是找到当前最小长度的窗口
- 在左边界右移过程中, 如果对应的某个元素计数已经是 0, 则再右移后该元素就不会再存在于当前窗口, 此时 unmatch 就要加 1, 之后就不再继续右移了
- 这样我们就找到了以当前右边界结尾的最小有效窗口, 用它来更新来最终结果
- 然后继续右移右边界, 循环上述过程即可
- 下面代码有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(B+S): 假设 B 是 big 数组的长度, S 是 small 数组的长度, 那么将 small 数组转计数字典需要 O(S)时间, 而滑动窗口部分需要 O(2*B)时间 (每个数字只会被访问两次) - 空间复杂度
O(S): 额外计数字典存储 small 的值与计数的映射
代码
class Solution:
def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
# 滑动窗口+计数字典+尚未匹配个数
n = len(big)
unmatch = len(small)
mnLen = float("inf")
# 先将small数组转成计数字典{val:cnt}
cnts = collections.Counter(small)
res = []
i = 0
for j in range(n):
if big[j] in cnts:
# 只考虑在small数组中的元素
if cnts[big[j]] == 1:
# 首次遇到该元素, 尚未匹配个数减1
unmatch -= 1
# 更新计数
cnts[big[j]] -= 1
if unmatch == 0:
# 全部匹配, 左边界向右移, 直到尚未匹配个数再次大于0
while unmatch == 0:
if big[i] in cnts:
# 只考虑在small数组中的元素
if cnts[big[i]] == 0:
# 当前元素计数为0, 再向右移时会导致当前数字不再匹配, 尚未匹配个数加1
unmatch += 1
# 更新计数
cnts[big[i]] += 1
i += 1
# 当前可以匹配所有数字的最小窗口就是[i-1,j]
curLen = j - i + 2
if curLen < mnLen:
# 如果当前窗口长度更小, 则更新最终结果
# 注意这里长度相等时不更新, 因为题目要求在有多个长度相等的最小窗口时, 返回左端点最小的一个
mnLen = curLen
res = [i - 1, j]
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号