滑动窗口的思路要把它的内涵给摸透，摸清楚，才是最重要的，遇到做题会举一反三
滑动窗口也是属于双指针的范畴，也是比较难得掌握的一点的部分，必须自己有十分清晰的做题套路。
滑动问题包含一个滑动窗口，它是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动，同时 动态地 记录一些有用的数据，很多情况下，减少while的循环，能够极大地提高算法地效率。
自己在练习的基础上，多多的总结与刷题，一些常用的技巧要能够真正掌握清楚才行。
参考链接：https://www.bilibili.com/video/BV1V44y1s7zJ?spm_id_from=333.337.search-card.all.click
这些题目有一个共同点：
关键字：
满足XXX条件（计算结果，出现次数，同时包含等）
最长/最短的
子串、子数组、子序列、最长、最小、长度最小等
滑动窗口的使用思路（寻找最长）：

1. 核心：左右双指针（L和R）在起始点，R向右逐位滑动循环
2. 每次滑动的过程中
   1. 如果窗口的元素满足要求，R向右扩大窗口，并更新最优结果
   2. 窗口内不满足要求，L向右缩小窗口
3. R到达结尾的地方
   寻找最短:
4. 核心：左右双指针（L和R）在起始点，R向右逐位滑动循环
5. 每次滑动的过程中
   1. 如果窗口元素满足条件，L向右缩小窗口，并更新最优结果
   2. 如果：窗内的元素不满足要求，R向右扩大窗口
6. R达到结尾
   做题的答题框架
   直接模板化，两者在内层循环中不太一样，一旦是想用滑动窗口的话就要想到这个模板，后期这个模板要成为自己的做题的一个常用套路

# 最长的情况：
初始化left right result bestResult
while 右指针没有到结尾:
    窗口扩大，加入right对应的元素，更新当前result
    while result不满足要求:
        窗口缩小，移除left对应的元素，left右移
    更新最优结果bestResult
    right+=1
返回bestResult

# 最短的情况：
初始化left right result bestResult
while 右指针没有到结尾:
    窗口扩大，加入right对应的元素，更新当前result
    while result满足要求:
        更新最优结果bestResult
        窗口缩小，移除left对应的元素，left右移
    right+=1
返回bestResult

结合labuladong的模板，也做一点相应的理解

left,right=0,0
while right <s.size:
    # 增大窗口
    window.add(s[right])
    right+=1
    while window needs shrink:
        # 缩小窗口
        window.remove(s[left])
        left+=1

难点：细节的处理，

1. 何时向窗口中添加新元素
2. 如何缩小窗口
3. 在滑动窗口的哪个阶段更新结果

主要解决以下的一些题目：

1. leetcoad3：无重复字符的最长子串(middle)
2. leetcoad209：长度最小的子数组(middle)
3. ** leetcoad219 存在重复元素II**（middle）
4. leetcoad76-最小覆盖子串（hard）
5. leetcoad438:找到字符串中所有字母异位词(middle)
6. leetcoad567:字符串的排列(middle)
7. leetcoad239:滑动窗口的最大值（hard）
8. leetcoad30-串联所有单词的子串（hard）
9. leetcoad187-重复的DNA序列
10. leetcoad643：子数组最大平均数（之前没有通过的）
11. leetcaod1456：定长子串中元音的最大数组

leetcoad-3：无重复字符的最长子串

题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

滑动窗口也是属于双指针的范畴，也是比较难得掌握的一点的部分。
滑动问题包含一个滑动窗口，它是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动，同时 动态地 记录一些有用的数据，很多情况下，能够极大地提高算法地效率。自己在练习的基础上，多多的总结与刷题，一些常用的技巧要能够真正掌握清楚才行。
参考链接：https://www.bilibili.com/video/BV1V44y1s7zJ?spm_id_from=333.337.search-card.all.click
一些关键的字眼：

1. 满足XXX条件（计算结果，出现次数，同时包含等）
2. 最长/最短的
3. 子串、子数组、子序列、最长、最小、长度最小等

滑动窗口的使用思路（寻找最长）：

1. 核心：左右双指针（L和R）在起始点，R向右逐位滑动循环
2. 每次滑动的过程中
   • 如果窗口的元素满足要求，R向右扩大窗口，并更新最优结果
   • 窗口内不满足要求，L向右缩小窗口
3. R到达结尾的地方

寻找最短:

1. 核心：左右双指针（L和R）在起始点，R向右逐位滑动循环
2. 每次滑动的过程中
   1. 如果窗口元素满足条件，L向右缩小窗口，并更新最优结果
   2. 如果窗内的元素不满足要求，R向右扩大窗口
3. R达到结尾

做题的答题框架
直接模板化，两者在内层循环中不太一样，一旦是想用滑动窗口的话就要想到这个模板，后期这个模板要成为自己的做题的一个常用套路

# 最长的情况：
初始化left right result bestResult
while 右指针没有到结尾:
    窗口扩大，加入right对应的元素，更新当前result
    while result不满足要求:
        窗口缩小，移除left对应的元素，left右移
    更新最优结果bestResult
    right+=1
返回bestResult

# 最短的情况：
初始化left right result bestResult
while 右指针没有到结尾:
    窗口扩大，加入right对应的元素，更新当前result
    while result满足要求:
        更新最优结果bestResult
        窗口缩小，移除left对应的元素，left右移
    right+=1
返回bestResult

难点：细节的处理

1. 何时向窗口中添加新元素
2. 如何缩小窗口
3. 在滑动窗口的哪个阶段更新结果
4. 如何进行结果的调试（特别是做题的时候）

以无重复字符的最长子串为例子
题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

回顾过最长回文子串的题目，发现和这题很像，这里简单回顾一下那道题的做法：

如果是采用暴力的解法：
遍历字符串，然后找到所有的子串（长度从1~该字符串的长度），判断每一个”子串”是否有重复字符，最终得到无重复最长子串。计算所有的子串的时间复杂度是O(n^2),然后再判断一个字符串中是否有重复的字符，又要从头遍历一遍该字符串，最终的时间复杂度为O(n^3).
相应的复杂度比较的高。
比如光是要求出字符串的子串，这种方式，这里演示一下：

# 写一个函数，用于找出一个字符串的所有子串
def sub(s):
    # 定义一个数组用来
    result=[]
    # 外层循环表示子串的起始位置
    for start in range(len(s)):
        # 内层循环表示子串的长度
        for length in range(len(s)-start):
            result.append(s[start:start+length+1])
    # 循环结束，返回所有的结果
    return result
s='abcde'
print(sub(s))
# 打印结果如下：
['a', 'ab', 'abc', 'abcd', 'abcde', 'b', 'bc', 'bcd', 'bcde', 'c', 'cd', 'cde', 'd', 'de', 'e']

如果是按照先求子串，再求不重复的子串，最后求最长的，这样的复杂度太高了。
这里再提供了一种暴力解法的思路（可以通过）：
通过比较相邻的元素，在不相等情况下保证新加入的元素和之前的字符串里面的元素没有重复，用count数组来记录无重复字符的子串的长度，循环找出所有的无重复字符的子串，找出其中最大的返回

class Solution:
    def lengthOfLongestSubstring(self, s):
        # count记录的是无重复字符的子串长度，初始值为1
        count=1
        subnum=[]
        i=0
        while i <len(s)-1:
            # 如果相邻的元素不相等，并且新加入的元素不在前面的字符串里面
            if s[i]!=s[i+1] and s[i+1] not in s[i+1-count:i+1]:
                count+=1
                i+=1
            else:
                # 将当前的子串的长度加入到subnum数组中
                subnum.append(count)
                # 同时要重新开始计算无重复字符的子串的长度
                count=1
                # 字符的索引值也要重新开始计算
                # 这里索引值的更新很巧妙，更新的索引值都是从无重复字符的子串的长度开始的
                i=len(subnum)
        # 循环结束后输出最大的值
        return max(subnum)       

下面采用滑动窗口的思路来解题（因为这种思路广泛用于字符中的，所以也是必须要掌握的）
分析题目是求最长的情况，直接套用最长时候的模板，以下的这个版本可能不是那么直观

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 套用最长的情况的模板
        # 初始化左右指针，过程结果以及最优结果
        left,right,length,max_length=0,0,0,0
        # 定义一个哈希set,用于储存
        hashset=set()
        # 外层的while循环右指针没有达到结尾
        while right <len(s):
            # 窗口扩大，加入right对应的元素，更新过程结果以及当前的最优结果
             if s[right] not in hashset:
                hashset.add(s[right])
                length+=1
                if length >max_length:
                    max_length=length
                # 右指针往右移动
                right+=1
            else:
                # 内层循环，while的条件是过程结果不满足要求
                # 右边的元素重复出现在了hashset中
                while s[right] in hashset:
                    # 窗口缩小，移除left对应的元素，left右移,同时过程结果-1
                    hashset.remove(s[left])
                    left+=1
                    length-=1
                # 内层循环结束，更新过程结果
                # 右边的元素又可以重新放入窗口
                hashset.add(s[right])
                right+=1
                length+=1
        # 返回最优结果
        return max_length

if __name__ == '__main__':
    s = "pwwkew"
    res=Solution().lengthOfLongestSubstring(s)
    print(res)

这里还看到一个更加好理解的版本，也作为学习的记录写在这里,这一版虽然思路差不多，但是写法上却又有细微差别，上一个用到了元组，这里用到了字典，都可以进行判重处理，两者在更新结果的位置也不同。两者都用到了两层循环来解题。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 初始化左右指针以及最优结果
        left,right,max_length=0,0,0
        # 建立一个哈希表,表示一个滑动的窗口
        window={}
        # 指针没有走到末尾
        while right <len(s):
            # 思考当right向右移动的时候，即加入字符，应该更新哪些数据
            # 元素c是要加入的元素
            c=s[right]
            # window中需要加入键值对
            window[c]=window.get(c,0)+1
            # 窗口右移
            right+=1

            # 现在思考：什么条件下窗口应该停止扩大，开始移动left,缩小窗口
            # 满足的条件是：新加入的元素在哈希表中出现了（用代码表示就是对应的哈希值>1）
            while window[c]>1:
                # 现在要思考：当移动left缩小窗口（即移除字符），需要更新哪些数据
                # d为需要移除的字符
                d=s[left]
                # 移除字符的哈希值要-1
                window[d]-=1
                # 同时左侧窗口右移
                left+=1
            # 思考何时应该更新结果
            # 内层循环都是不满足条件，要想满足条件并且要最大，就在内层循环结束后进行结果的更新
            max_length=max(max_length,right-left)
        return max_length

if __name__ == '__main__':
    s = "pwwkew"
    res=Solution().lengthOfLongestSubstring(s)
    print(res)

leetcoad209：长度最小的子数组

题目描述：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
第一次自己写，失败
失败原因如下：

1.

采用滑动窗口的思路

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 初始化
        left,right,result,minlength=0,0,0,0
        # while 右指针没有到结尾
        while right<len(nums):
            # 窗口扩大，加入right对应的元素，更新当前的result
            result+=nums[right]
            # while result 满足要求：
            while result>=target:
                # 更新最优结果besrResult
                if right-left+1<minlength or minlength==0:
                    minlength=right-left+1
                # 窗口缩小，移除left对应的元素，left右移
                result-=nums[left]
                left+=1
            # 更新最优结果minlength
            right+=1
        return minlength

后面自己有用滑动窗口写了一版

from typing import List
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 要求长度最小的子数组
        # 分析题意，要连续的子数组满足之和大于一个目标值，并且在这些符合条件的基础上再找出一个长度最小的
        # 采用滑动窗口的思路，并套用最短的模板
        # 初始化
        left,right=0,0
        # 定义记录连续子数组的长度以及最小长度的
        length=0
        min_length=float('inf')
        # 定义一个哈希表，用来存放当前窗口的元素
        # window={}

        # 下面开始两个窗口的移动
        # 由于是要求长度最小的，所以应该是内层循环中更新最小的结果
        while right <len(nums):
            # 窗口右移，同时长度+1
            length+=1
            right+=1
            # 下面开始对左侧的窗口进行移动
            # while循环中应该写满足的条件
            while sum(nums[left:right])>=target:
                # d=nums[right]
                # 左侧的窗口右移，同时更新一些数据
                length=right-left
                # 更新最优结果
                if length < min_length:
                    min_length=length
                left+=1
        # 返回最优结果
        return min_length
   

if __name__ == '__main__':
    nums= [2,3,1,2,4,3]
    target=7
    res=Solution().minSubArrayLen(target,nums)
    print(res)

leetcoad219-存在重复元素II（easy）

理解题意：
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
暴力解题，只能通过40%的算例

1. 我们可以从前往后遍历 numsnumsnums，同时使用 Set 记录遍历当前滑窗内出现过的元素。
2. 假设当前遍历的元素为 nums[i]：
   1. 下标小于等于 k（起始滑窗长度还不足 k+1）：直接往滑窗加数，即将当前元素加入 Set 中；
   2. 下标大于 k：将上一滑窗的左端点元素 nums[i−k−1] 移除，判断当前滑窗的右端点元素 nums[i] 是否存在 Set 中，若存在，返回 True，否则将当前元素 nums[i] 加入 Set 中。

重复上述过程，若整个 numsnumsnums 处理完后仍未找到，返回 False。
解题思路有两种：

1. 暴力解法（通不过全部实例）
2. 哈希表
3. 滑动窗口

暴力解法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 直接暴力解法，思路没有错
        n=len(nums)
        for i in range(n):
            # 另一个数字与当前数字的索引差值小于等于k
            for j in range(i+1,n):
                if j-i<=k and nums[i]==nums[j]:
                    return True
                else:
                    continue
        return False

哈希表的解法：

from typing import List
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 建立一个hashmap
        # key:存储元素，value：储存下标
        hashmap={}
        # 遍历数组
        for i,num in enumerate(nums):
            # 如果发现元素是在哈希表里面，并且当前的下标与哈希表中另一个相同值的下标的索引值相差小于等于k
            if num in hashmap and i-hashmap[num]<=k:
                return True
            
            # 将nums[i]和i存入hashmap中
            # 使用hashmap记录每个元素的最大下标
            hashmap[num]=i
        # 循环结束之后还是没有找到两个元素相等并且下标只差小于等于k的，直接返回False
        return False
if __name__ == '__main__':
    nums= [1,2,3,1]
    k=3
    res=Solution().containsNearbyDuplicate(nums,k)
    print(res)

采用滑动窗口的解法一：

from typing import List
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 建立一个hashset
        hashset=set()
        for i,num in enumerate(nums):
            # 如果发现下标大于k,即不满足要求
            if i >k:
                # 移除左边的元素
                hashset.remove(nums[i-k-1])
            # 如果发现元素已经在hashset中存在的话,表明是符合题目的要求的
            if num in hashset:
                return True
            # 继续往hashset中添加值
            hashset.add(num)
        # 当循环结束的时候，还是没有找到符合条件的情况
        return False
            
if __name__ == '__main__':
    nums= [1,2,3,1]
    k=3
    res=Solution().containsNearbyDuplicate(nums,k)
    print(res)

滑动窗口解法二：

想用到模板的，有助于理解模板,其实还可以写一个版本的

from typing import List
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 分析题目的意思：索引不同，并且相应的索引差值的绝对值不超过K，同时这两个数要相等
        # 现在采用滑动窗口的思路
        left,right=0,0
        hashset=set()
        # 用两层循环不断地加入新元素和移除新的元素
        while right<len(nums):
            c=nums[right]
            right+=1
            if c not in hashset:
                hashset.add(c)
            # 当该元素在哈希表中的时候，可以直接返回True
            else:
                return True
            while right-left>k:
                d=nums[left]
                # 将左侧的元素移除
                hashset.remove(d)
                left+=1
        # 两层循环结束之后都没有找到符合要求的
        return False
            
if __name__ == '__main__':
    nums= [1,2,3,1]
    k=3
    res=Solution().containsNearbyDuplicate(nums,k)
    print(res)

但是用这种方式属实是有点不太好理解，单纯是为了熟悉模板，所以自己也圈出了需要注意的点如下：

leetcoad220-存在重复元素(搁置)

题目要求如下：
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false
相比上一题，这一题的话有多加入了一个条件：两者数值的绝对值只差不超过t值
暴力解题，通过95%的算例

# 暴力解法，实际不能这样写
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        # 直接暴力解法，思路没有错
        n=len(nums)
        for i in range(n):
            # 另一个数字与当前数字的索引差值小于等于k
            for j in range(i+1,n):
                if j-i<=k and abs(nums[i]-nums[j])<=t:
                    return True
                else:
                    continue
        return False

采用滑动窗口的思路来解题

会超时，有时间整理这里的代码
对于任意一个位置 i（假设其值为 u），我们其实是希望在下标范围为 [max(0,i−k),i)内找到值范围在 [u−t,u+t]的数。
最基础的想法：每次遍历到任意位置i的时候，往后检查k个元素，需要优化检查后面k个元素的过程
进一步的思路：用一个有序的集合去维护长度为k的滑动窗口的数，能够支持高效查询与插入和删除的操作

leetcoad76-最小覆盖子串（hard）

备注：说实话这道题对于初学者来说真的是有点难，而且思路很离奇，只要是没有做过的，也是一定想不出来,可能刚开始看题目都没有看懂，或者是完全一脸懵逼，所以还是得死磕
题目解读：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
1. 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
2. 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
示例2：
输入：s = “a”, t = “a”
输出：”a”
示例3：
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

使用暴力解法

for i in range(len(s)):
    for j in range(i+1,len(s)):
        if s[i:j] 包含t的所有字母：
            更新答案

采用滑动窗口的思路

1. 在s中使用左右指针的技巧，[left,right)为一个滑动窗口,是一个左闭右开的区间
2. 先不断地增加right指针扩大窗口[left,right),直到窗口的字符串符合要求（包含 t中所有的字符：这里的转换关系很重要）【寻找一个可行解】
3. 停止增加right，转而不断地增加left，缩小窗口，[left,right),直到窗口地字符串不再符合要求（不包含t中的所有字符：同样的也是转换关系），每次增加left，都要更新一轮结果【优化一个可行解】
4. 重复2 3 步直到right达到字符串的尽头【最终找到最优解】
   理解：这里面的左右指针轮流前进，窗口大小增增减减，窗口不断地向右滑动，也即滑动窗口地来历。（这里面的思维十分的到位，不光是理解，更要到应用的层面上来，即如何去实现它）
   想象：一个窗口在字符串上游走，当这个窗口包含的元素满足条件（包含字符串t的所有元素），记录这个滑动窗口的长度（right-left+1），这些长度中的最小的值就要求的结果。
   need和window相当于计数器，分别记录T中字符出现的次数和窗口中相应字符出现的次数
   初始状态：
   
   增加right，直到窗口[left,right]包含了T的所有字符
   
   然后增加left，缩小窗口[left,right]
   
   直到窗口中的字符串不在符合要求，left不再继续移动
   
   之后重复上诉的过程，先移动right，再移动left……，直到right指针达到字符串s的末端，算法结束（这个过程是一个动态的过程，很考验自己的抽象思维能力！！！）

框架如何使用

step1:初始化window和need两个哈希表，记录窗口中的字符和需要凑齐的字符

need,,window={},{}

step2:使用left和right变量初始化窗口的两端，初始情况下，窗口没有包含任何字符

left,right=0,0
count =0
while right<len(s):
    # 开始滑动

count表示窗口中满足need条件的字符个数（条件满足，但是个数不一定满足），如果count和need.size的大小相同，则说明窗口已经满足条件，已经完全覆盖了串t
以下是模板的过程，需要思考以下的四个问题：（仔细地揣摩和理解）

1. 当移动right扩大窗口，即加入字符时，应该更新哪些数据？（每道题的特色变化）
2. 什么条件下，窗口应该停止扩大，开始移动left来缩小窗口？（思维盲点）
3. 当移动left缩小窗口，即移除字符的时候，应该更新哪些数据？（每道题的特色变化）
4. 我们要的结果应该在扩大窗口还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加window计数器；相反，如果一个字符移除窗的时候，应该减少window计数器，当count满足need时应该收缩窗口，应该在收缩窗口的时候更新最终的结果。

import numpy as np
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 构建两个哈希表，分别存储需要凑齐的字符和窗口的字符
        need=dict((c,t.count(c)) for c in t)
        window={}
        # 使用left和right变量初始化窗口的两端
        # 等右指针所在的位置之前的字符串包含t以后，左指针开始移动
        left,right=0,0
        # 用于记录满足need条件的子串的长度
        count=0
        # 记录最小覆盖子串的起始索引及长度
        start=0
        min_length=np.inf
        while right<len(s):
            # 将字符c移入窗口
            c=s[right]
            # 右移窗口
            right+=1
            # 进行窗口内一系类数据的更新
            # 如果c在need的关键字中
            if  c in need.keys():
                window[c]=window.get(c,0) +1
                if  window[c]==need[c]:
                    count+=1
            # debug输出的位置一：表明此时的窗口
            print("window向右扩充:", left, right)
            # 判断左边的窗口是否需要收缩
            # while的条件是满足要求：有效的计数个数=需要的长度，此时循环结束
            while count ==len(need):
                # 在这里更新最小的覆盖子串
                if right - left <min_length:
                    start = left
                    min_length=right-left
                # d是将移除窗口的字符
                d=s[left]
                # 左移窗口
                left+=1
                # 进行窗口内一系列数据的更新
                if d in need.keys():
                    window[d]-=1
                    # 这里的判断是非常有必要的，而且往往是被忽略的，也就是说这个count-1是有一定的条件的。
                    if window[d] <need[d]:
                        count-=1
        # 返回最小的覆盖子串
        if min_length==np.inf:
            return ''
        else:
            return s[start:start+min_length]


if __name__ == '__main__':
    s= "EBBANCF"
    t= "ABC"
    res=Solution().minWindow(s,t)
    print(res)

自己第二次写的时候有以下几点没有把握住：

1. 因为加入的元素可能会有相同的情况，所以在count更新之前必须要加入判断
2. 移除元素的时候同理，也要加入判断，而且判断要合理：在一个调试出错的例子中：s=’aa’,t=’aa’,如果判断写成

# 如果判断条件写成这样，就会出现问题
if window[d]<1 :
    counyt-=1
# 打印结果
'a'
# 而实际正确的结果应为'aa'

leetcoad438:找到字符串中所有字母异位词

题目解读：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
另类的解释：相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
第一写，存在问题
存在问题的原因：自己是用的暴力的解法，想用哈希表来更新符合条件的索引值，但是无论是符合还是不符合，索引值都会更新（这个不太符合要求！！！！！！）

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 构建两个哈希表
        need=dict((c,p.count(c)) for c in p)
        window={}
        left,right=0,0
        # 创建一个结果数组，用于存放所有满足条件的起始索引
        res=[]
        count=0
        # right指针没有走到末尾
        while right<len(s):
            # 加入c字符，同时窗口向右
            c=s[right]
            right+=1
            # 进行窗口的一系列更新
            # 如果发现遍历的元素出现在need的key值里面，将该键值对加入window哈希表中，其中计数右默认的0再增加1（后面再次出现再+1）
            if c in need.keys():
                window[c]=window.get(c,0)+1
                # 查看当前两个哈希表中对应的计数值是否相等，如果相等，则有效的子串长度+1
                if window[c]==need[c]:
                    count+=1
            
            # 加入一段调试代码
            print('window:',left,right)
            # 判断左侧的窗口是否要收缩
            # while循环里面要写结果不满足要求的情况
            #while right - left >len(p):
            while count==len(need):
                # 当窗口符合条件时，把起始索引加入res中（此时子串的计数等于need的长度）
                #if count==len(need):
                if right-left==len(p):
                    res.append(left)
                # 字符d为左边将要移除的元素
                d=s[left]
                # 左侧的窗口右移
                left+=1
                # 进行窗口内一系列数据的更新
                # 如果d出现在need哈希表的key值中
                if d in need.keys():
                    # 判断两个哈希表中d的计数是否相等
                    # 如果相等的化，就需要把子串计数-1
                    if window[d]==need[d]:
                        count-=1
                    # 把window中d的计数-1
                    window[d]-=1
        # 循环结束
        return res

再次做的时候，发现有以下的几个小点需要特别注意（好像都是这些题目的共性问题）
后面从纵向把这些题目拿来一起进行比较分析就可以得出一些规律以及哪些坑是可以避免的。

leetcoad567:字符串的排列

题目解读：
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).
初步分析：

1. 输入的 s1 是可以包含重复字符的，所以这个题难度不小。
2. 这种题目，是明显的滑动窗口算法，相当给你一个 S 和一个 T，请**问你 S 中是否存在一个子串，包含 T **

题解思路：
对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

1. 本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。
2. 当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
   至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。
   自己做的感受：思维卡壳，通不过呀！！！，而且写的是没有一点灵魂，而且里面有一些很细节部分。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # 特殊情况
        if len(s2)<len(s1):
            return False
        # 仍然采用滑动窗口的思路来解题
        # 具体的思维如下：
        # 1. 在向右滑动的过程中不断往window加入碰到的need哈希表中的值，并且还要计数
        # 2. 在左侧窗口向右滑动的过程中始终保持计数值和need的长度相等，并且需要在此时窗口的长度等于需要匹配的字符的长度的时候更新结果
        left,right=0,0
        # 构建一个need哈希表，表中存放的是s1中的每个元素以及计数（1）
        need=dict((i,s1.count(i)) for i in s1)
        window={}
        # 定义一个变量用来记录次数
        count=0
        while right < len(s2):
            # 字符c是即将要向右加入的元素
            c=s2[right]
            if c in need.keys():
                window[c]=window.get(c,0)+1
                if window[c]==need[c]:
                    count+=1
            right+=1

            # 现在进入内循环，注意思考while 循环的条件以及何时对结果进行更新
            while count==len(need):
                # 如果发现此时的两个左右指针间的差值正好等于s1的长度
                # 能够进入内层循环，说明，说明当前窗口有目标字符，再加入这个条件的限制就正好是输出的结果
                if right- left ==len(s1):
                    return True
                # d是即将要从左侧窗口移除的元素
                d=s2[left]
                # 和外层的循环对称使用
                if d in need.keys():
                    window[d]=window.get(d,0)-1
                    if window[d]<need[d]:
                        count-=1
                left+=1
        # 循环结束之后仍没有找到
        return False

做题之后的反思：很容易就想错的几个点

1. 假如存在相同的多个元素的情况，比如：s1=”abc”,s2=”ccccbbbbaaaa”
2. 还有一个需要注意的点就是，内存循环更新count时的判断语句能否和外层的一样？这样写有什么问题if window[d]==need[d]:,这里用另外的一个例子来说明： s1=”ab”,s2=”eidboaoo”
   这里我也做了一个调试的情况写在这里了

# 针对第一种易错点
# 举的例子是 s1="abc",s2="ccccbbbbaaaa"
# 如果外层循环是这样写的
while right < len(s2):
            # 字符c是即将要向右加入的元素
            c=s2[right]
            if c in need.keys():
                window[c]=window.get(c,0)+1
                count+=1
                # if window[c]==need[c]:
                #     count+=1
            right+=1

直接三个c进入，程序直接结束，这肯定是不对的，同样的对于s1=”ab”,s2=”eidboaoo”，也有类似的情况

# 针对第二种错误，为什么这样写就是有问题的
# 举的例子是s1="ab",s2="eidboaoo"
while count==len(need):
                # 如果发现此时的两个左右指针间的差值正好等于s1的长度
                # 能够进入内层循环，说明，说明当前窗口有目标字符，再加入这个条件的限制就正好是输出的结果
                if right- left ==len(s1):
                    return True
                # d是即将要从左侧窗口移除的元素
                d=s2[left]
                # 和外层的循环对称使用
                if d in need.keys():
                    window[d]=window.get(d,0)-1
                    if window[d]==need[d]:
                    # if window[d]<need[d]:
                        count-=1
                left+=1

用这组例子的时候我们发现结果应该是False，结果返回的却是True.应为”boa”这种情况是不对的，题目的要求是子串，这个只是含有ab组合，却不是真的ab的组合，本来有一个限制条件：

 if right- left ==len(s1):
    return True

原因就在于，当我将判断条件设定为”if window[d]==need[d]:”的时候，在向左滑动窗口的时候发现，当b被移除窗口的时候，此时因为window[d]!=need[d]:所以判断直接跳过，并没有执行coun-=1,导致此时居然是满足内层循环的条件，紧接着又满足了”if right- left ==len(s1):”,直接返回了True.
正确的做法：将此时的判断条件改为： if window[d]<need[d]:，那么当b从左侧窗口移除的同时，相应的 count-=1,这样内层循环的条件就不满足，于此再次跳到外层循环，右侧窗口继续扩大，继续循环。

三道题的总结与反思

上面的最小覆盖子串、字符串的排列 以及找出所有字符串的异位词，解题的代码十分的相似，差别的点不是太多，只是需要稍微的改动一下就可以通用，关键还是要理清楚更新结果的位置，在哪里更新以及怎么更新，这三道题我认为已经体现得淋漓尽致了，是一个很好的值得记录和后面牢牢掌握的点，相信自己对滑动窗口的题目又有了新的认识，之后碰到这样的题目能够把框架思维给利用上去。

leetcoad239-滑动窗口的最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
https://www.algomooc.com/635.html
解题的本质：
将处于窗口的第一个数字删除，同时在窗口的末尾添加一个新的数字，可以用双端队列来模拟，每次把尾部的数字弹出，再把新的数字压入到头部，然后找栈队列中最大的元素。
如果队列中进来一个较大的数字，那么队列中比这个数字更小的数字就不可能再成为窗口中最大的元素了（这个大的数字是后进来的，一定会比之前早进入窗口的小的数字要后离开窗口，先进入且比较小的数字必然不可能成为最大的元素，可以弹出队列）

注意事项：
python中队列保留的是索引，而其他的像java和C++中队列保存的是元素

解题步骤如下:
* 获取数组长度
* 构建双端队列
* 创建一个存储最大值的数组
* 定义好相应的边界情况
* 一开始滑动窗口不包含K个元素，不是合格的滑动窗口

        * 在滑动的过程中，维护好deque,确保是单调递减队列
        * 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将元队尾素移除（为什么要移除队尾元素：因为前面已经进行递减的操作了）。
        * 直到考察元素可以放入到队列中（此处采用while循环进行相应的判断：满足条件就不断的执行队首元素的弹出，不满足：即考察的元素小与队列的队尾元素就加入进去）

* **当滑动的窗口正好有k个元素的时候，那么最大值就是对应的队首元素**

    * **向右移动会把窗口最左边的给舍弃**
    * 加入判断语句，如果队首元素与窗口最左边的元素相等，需要将队首元素抛出
    * 反复判断，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除（采用while循环进行相应的判断，与上面的判断相同，相等的情况也要进行弹出）
    * 直到考察元素可以放入到队列中
* 最后返回res

代码如下：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        res = []

        if n ==0 or k ==0:
            return res
            
        for i in range(0,k):

            while q and nums[q[-1]] <= nums[i]:
                q.pop()
            q.append(i)
        res.append(nums[q[0]])

        for i in range(k,n):
            while q and q[0] <= i - k:
                    q.popleft()
            while q and nums[q[-1]] <=nums[i]:
                q.pop()
            q.append(i)
            res.append(nums[q[0]])
        return res

第一种写法：
while q and nums[q[-1]] <= nums[i]:
q.pop()
q.append(i)
第二种写法：
while q and q[-1] < nums[i]:
q.pop()
q.append(nums[i])

第二种代码如下：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        res = []


        if k < 1:
            return res

        for i in range (k):
            while q and q[-1] < nums[i]:
                q.pop()
            q.append(nums[i])
        res.append(q[0])

        for i in range (k, n):
            if q[0] == nums[i-k]:
                q.popleft()

            while q and q[-1] < nums[i]: 
                q.pop()
            q.append(nums[i])
            res.append(q[0])
        return res

    这里既然讲到了双端队列的问题，就做一点相应的知识整理：
    https://www.jb51.net/article/183382.htm  这里面讲的也很清楚明白
    **创建双向对队列：**
    import collections
    d = collections.deque()
    append(往右边添加一个元素)
    appendleft（往左边添加一个元素）
    clear(清空队列)
    copy(浅拷贝)
    count(返回指定元素的出现次数)
    ......