题目

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

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

示例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]
输出: []

分析： 滑动窗口算法

class Solution:
    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
        need = len(small)
        num_dict = {}
        for num in small:
            if num not in num_dict:
                num_dict[num] = 1
            else:
                num_dict[num] += 1
        n = len(big)
        i=j=0
        min_length = n
        num_index = []
        while i < n and j <= n:
            if need <= 0:
                if j - i <= min_length:
                    min_length = j - i - 1
                    num_index = [i, j-1]
                if big[i] in num_dict:
                    num_dict[big[i]] += 1
                    if num_dict[big[i]] > 0:
                        need += 1
                i += 1
            else:
                if j < n and big[j] in num_dict:
                    if num_dict[big[j]] > 0:
                        need -= 1
                    num_dict[big[j]] -= 1
                j += 1
        return num_index