程序员面试金典 - 面试题 17.18. 最短超串

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

• 假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。

• 返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。

示例 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

题目思考

1. 如何快速找到包含关系?

解决方案

思路

• 分析题目, 一个很容易想到的方案就是暴力两重循环:
  • 外层循环 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

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

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

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