题解 | #牛牛的串联子串游戏#滑动窗口

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param words string字符串一维数组 
# @return int整型一维数组
from collections import Counter
class Solution:
    def findSubstring(self , s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        word_size = len(words)
        valid = 0
        total_len = word_len * word_size
        left = 0
        need = Counter(words)  # 统计单词列表中每个单词的出现次数
        window = Counter()
        res = []

        for r in range(0, len(s), word_len):

            word = s[r:r + word_len]
            if word in words:
                window[word] += 1
                if window[word] == need[word]:
                    valid += 1

            while r - left + word_len == total_len:
                if valid == word_size:
                    res.append(left)

                if s[left:left + word_len] in need:
                    if window[s[left:left + word_len]] == need[s[left:left + word_len]]:
                        valid -= 1
                    window[s[left:left + word_len]] -= 1

                left += word_len

        return res

定义两个字典need和window，分别用来存放条件和当前遍历到的单词，valid用来判断是否为正确答案

每遍历到一个单词，加入window，并和need比较，若单词在need中，valid++

然后进入循环判断滑动窗口是否要缩小的条件为：r-left+单词长度==words中单词长度和

若valid == words中单词个数，加入正确答案

然后对left对应的单词做判断，在need中，valid--，然后window--

最后left+=单词长度