[TOC]

借鉴：https://www.cnblogs.com/huansky/p/13488234.html

​ https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solutions/1362316/by-dodo_1202-cqbe/

滑动窗口

滑动窗口是在给定大小的数组和字符串上进行平滑操作，找到指定内容的方法。由于需要两指针，因此通常需要一些辅助方法，如哈希表（即python中的dict,用于标记元素位置），或集合（即python中的set(),创建一个无序不重复元素集），优先队列，红黑树，单调队列，大小堆等等，应根据各种数据结构的特点来选取。

思考（也是考点）：

1、窗口使用什么数据结构
2、达到窗口限定后，左边届该怎样收缩，如果无法以常规方法收缩，考虑延时删除策略（在采集答案前进行）
3、怎样采集答案
4、滑窗的步长
5、滑窗的起始位置
6、是否需要数据预处理，例如排序，才能使用滑窗

大体思路

1、对字符串 S（或数组） 使用双指针中的左右指针技巧，初始化left = right = 0。 索引闭区间[ left,right]称为一个窗口。

2、不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）

3、停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第2 步和第三步，直到right到达字符串S的尽头

第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和窗口中的相应字符的出现次数。

初始状态：

增加 right，直到窗口 [left, right] 包含了 T 中所有字符：

现在开始增加 left，缩小窗口 [left, right]。

直到窗口中的字符串不再符合要求，left 不再继续移动。

之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。

寻找最长

【如果】窗内满足条件， R 向右扩大窗口,并更新最优结果

【如果】不满足条件， L向右缩小窗口

寻找最短

【如果】窗内满足条件， L 向右缩小窗口,并更新最优结果

【如果】不满足条件， R向右扩大窗口

例题：[30. 串联所有单词的子串 - 力扣（LeetCode）](https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

import collection
def Sliding Window(s,t): # t即题目中的words
    n = len(s)
    stride = len(t[0]) #定义步长
    limit = len(words) * stride
    

    #它的其他功能与dict相同，但会为一个不存在的键提供默认值，从而避免KeyError异常。    
    needs = collections.defaultdict(int)
    ans = []
    
    for w in t:
        need[w] += 1 
    for strat in range(0,stride):
        left = right = strat #指向当前步子的第一个下标
        cnt = 0 #记录窗口内满足要求得单词数
        window = collections.defaultdict(int)
		while right < n:
            #右边界入窗
            cur_right = s[right:right+stride]
            if cur_right in need:
                window[cur_right] += 1
               if window[cur_right] == need[cur_right]:
                	cnt += 1
            # 左边界收缩
            if right - left + stride > limit:
                cur_left = s[left:left+stride]
                if cur_right in need:
                    if window[cur_left] == need[cur_left]:
                        cnt -= 1
                    window[cur_left] -= 1
                    left += stride
            #采集答案
            if right - left +stride == limit and cnt == len(need):
                ans.append(left)
            right += stride
	return ans
            
                           

模板

本模板左右平移步长为1

import collection
def Sliding Window(s,t):
    left = right = 0
    valid = 0 # 窗口内已凑齐的字符种类数量
    window = collections.defaultdict(int)
    needs = collections.defaultdict(int)
    for w in t:
        needs[w] += 1
    while right < len(s):
       	#右边界入窗，对窗口内数据的一系列更新
        window[s[right]] += 1
        if window[s[right]] == need [s[right]]:
            valid += 1
        # 注意，先判断再加
        
        #判断左侧是否要收缩
        while 需要收缩:
            #左边界移除窗口，进行窗口内数据更新
            if window[s[left]] == need[s[left]]:
                valid -= 1
                #先判断再减
            window[s[left]] -= 1
            left += 1 # 注意左侧进行收缩
        
        采集答案
        right += 1