leetcode [17.18] 最短超串

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

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

滑动窗口

class Solution:
    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
        if len(small) > len(big): return []
        if len(small) == len(big):
            count1 = {b: 1 for b in big}
            count2 = {s: 1 for s in small}
            return [0, len(small) - 1] if count1 == count2 else []

        count = {s: 1 for s in small}
        ans = []
        left = 0
        match = 0
        for right, b in enumerate(big):
            if b not in count:
                continue
            count[b] -= 1
            if count[b] == 0:
                match += 1
            while match == len(small): #sum(1 for v in count.values() if v > 0) == 0:
                if not ans or right - left < ans[1] - ans[0]:
                    ans = [left, right]
                if big[left] in count:
                    if count[big[left]] == 0:
                        match -= 1
                    count[big[left]] += 1
                left += 1
        return ans