难度: Medium
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 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 <= 1000001 <= small.length <= 100000运行时间: 73 ms
内存: 30.2 MB
class Solution:
def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
if len(big) < len(small):
return []
cnt = {x: 1 for x in small}
n = len(big)
need = len(small)
min_len = n + 1
left = right = 0
ans = []
for right, num in enumerate(big):
if num in cnt:
if cnt[num] > 0:
need -= 1
cnt[num] -= 1
while left < n and need == 0:
if right - left + 1 < min_len:
min_len = right - left + 1
ans = [left, right]
if big[left] in cnt:
if cnt[big[left]] >= 0:
need += 1
cnt[big[left]] += 1
left += 1
return ans
本题解采用了滑动窗口的策略来找到包含所有'small'数组元素的最短子数组。首先，使用字典'cnt'来记录'small'中每个元素的计数，此时每个元素的计数初始化为1。接着，定义两个指针'left'和'right'表示当前窗口的左右端点，并使用变量'need'来表示还需包含的'small'数组的元素数。通过移动'right'指针扩展窗口，并在每次移动时更新'cnt'和'need'。当'need'为0时，说明窗口已包含所有'small'的元素，此时尝试通过移动'left'指针缩小窗口以寻找更短的子数组。每次更新窗口时都检查并更新最小长度的子数组。如果在整个过程中找到了符合条件的子数组，则记录其起始和结束位置。
时间复杂度: O(n)
空间复杂度: O(m)
class Solution:
def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
if len(big) < len(small):
return []
cnt = {x: 1 for x in small} # 初始化small中元素的计数
n = len(big)
need = len(small)
min_len = n + 1 # 初始化最小长度大于可能的最大长度
left = right = 0
ans = []
for right, num in enumerate(big):
if num in cnt:
if cnt[num] > 0:
need -= 1 # 减少需要的元素数量
cnt[num] -= 1 # 更新窗口内元素计数
while left < n and need == 0: # 当包含所有small元素时尝试缩小窗口
if right - left + 1 < min_len:
min_len = right - left + 1
ans = [left, right] # 更新最短子数组
if big[left] in cnt:
if cnt[big[left]] >= 0:
need += 1 # 重新增加需要的元素数量
cnt[big[left]] += 1 # 更新窗口内元素计数
left += 1 # 移动左指针
return ans
在`cnt`字典中，每个元素的计数初始化为1是为了表示每个元素最初都需要在`big`数组中被找到一次来满足条件。这个计数随着在`big`数组中找到相应元素而递减，直到0表示该元素的需求已经被满足。此外，初始化为1有助于通过`need`变量追踪还需要多少不同的元素才能满足条件，每发现一个新元素，`need`就减1，从而控制何时开始尝试缩小窗口求解最小长度子数组。
在`big`数组中某个元素的计数如果已经是负数，这表示该元素在当前窗口内出现的次数已经超过了`small`数组中的需求次数。在这种情况下，减少`need`值并不是由于找到了未满足需求的新元素，而是在首次遇到该元素时已经减少了`need`，后续即便出现计数为负的情况，也不应再次修改`need`。因此，实际代码中仅在`cnt[num] > 0`时，即这是首次或者是满足需求的情况下才减少`need`。如果计数为负，说明元素已经过量，不影响`need`的值。
在缩小窗口时检查`cnt[big[left]] >= 0`是为了确定减少窗口左边界时是否会导致某个在`small`数组中的元素不再满足需求条件。如果`cnt[big[left]] >= 0`，这意味着移除这个元素后，它在窗口中的数量将少于`small`数组中的需求数量，因此需要增加`need`，表示现在需要再次找到这个元素。如果`cnt[big[left]]`小于0，则表示即使减去这个元素，窗口中仍然有足够数量的该元素满足`small`的需求，因此不需要增加`need`。