面试题 17.18.最短超串

1. 题目描述

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

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

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

标签 数组 哈希表 滑动窗口

2. 解题

• map<int, int> need：记录要完全覆盖small数组，滑动窗口内需要覆盖的数字及其对应的个数
• int diff：记录要完全覆盖small数组，滑动窗口内需要覆盖的数字总个数
• int l：指向窗口的左边界
• int r：指向窗口的右边界
• int minLen：表示满足条件的最短子数组长度

1. 思路：

need是一个字典，用来存储要包含small数组中的所有元素还需要覆盖的各个数字的数量。diff记录需要覆盖的所有数字的总数，diff的增大与减小与need是同步的，但是diff必须大于等于0。

那么，当我们遍历big中的数字a时，如果数字a在small中出现，那么我们将need[a]减一，说明窗口内增加了一个a，需要a的数量减一；

注意：need[a]是可能为负数的，为负数说明当前窗口内的元素a超过了数组small中的元素a的数量

如果，数字a在small中未出现，说明该数字对是否包含small是完全没有影响的，不用执行任何操作；

然后，当访问数组big中的数字一直到某个位置时，need中的所有键对应的值都为0，diff也等于0，此时当前窗口已经包含了small数组里的所有元素，甚至多余。记录当前窗口的长度len，并将左指针l右移，寻找包含small数组的最大下标l（即最短区间）

我们只需要找到完整包含small数组的最短区间[l, r]即可。

2）步骤：

• 使用small数组初始化need，need存储small中的所有元素
• 使用左、右指针l和r遍历big数组
• 如果区间[l, r]内的元素未完全覆盖small(即diff != 0)，r右移
• 如果区间[l, r]内的元素完全覆盖small(即diff == 0)，l右移，压缩区间，直到区间[l, r]不完全覆盖small数组
• 重复步骤3-4，直到找到完全覆盖small数组的最短区间[l, r]