最近迷上了leetcode刷题，滑动窗口可以说是leetcode入门必会技巧了，这里通过写题的过程重新复习一遍。

leetcode：LCR 016无重复字符的最长字串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入: s = “” 输出: 0

首先分析一边题目，题目要求给定字符串无重复字符的最长字串，注意，字串必须是内部连续的，不能跳跃，这就给了滑动数组发挥空间。
在使用滑动数组之前要确认几件事情：
1，数组长度是否可变
2，该使用哪种数据结构记录滑动窗口
由题意可得，数组长度可变，同时是判断滑动窗口内是否有重复字符，故可以使用集合set来判断是否重复

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        找到字符串中没有重复字符的最长子串的长度
        注意是字串而不是子序列
        :type s: str
        :rtype: int
        """
        temp=set()
        left=0
        right=0
        max_len=0
        while right<len(s):
            temp.add(s[right])
            right+=1
            max_len=max(max_len,right-left)
            while right<len(s) and s[right] in temp :
                temp.remove(s[left])
                left+=1
        return max_len
if __name__=='__main__':
    s='abcabcbb'
    print(Solution().lengthOfLongestSubstring(s))

为一值得注意的即为判断右侧字符是否在temp中时，要限定右侧字符的范围，否则可能会出现越界的错误

leetcode：209长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [nums_l, nums_l+1, …, nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4] 输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

同样，分析题目，显然不是定长，而是通过sum来维护数组，故滑动窗口目的为维护一个数组和，当和小于target时，向右扩展数组，并记录当前数组长度；当大于等于target时，向左收紧数组，直到sum小于等于target。最后返回最短数组长度。
代码如下：

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        """
        找出数组中连续子数组的最小长度，该子数组的和大于等target
        :param target:
        :param nums:
        :return:
        """
        sum=0
        left=0
        right=0
        max_len=len(nums)
        for i in range(len(nums)):
            sum+=nums[i]
        if target>sum:
            return 0
        sum=0
        while right<len(nums):
            sum+=nums[right]
            right+=1
            while sum>=target:
                max_len=min(max_len,right-left)
                sum-=nums[left]
                left+=1
        return max_len
if __name__ == '__main__':
    print(Solution().minSubArrayLen(7,[2,3,1,2,4,3]))

leetcode：567字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：

输入：s1= “ab” s2 = “eidboaoo” 输出：false

由题意可得，这次是维护一个定长的窗口，同时仅仅只是判断该窗口是否为给定字符串的排列，故可以使用python中的数据结构Counter，通过判断Counter相等来得到是否为排列，不过要注意，当对应键值对为0时要记得删除这个键，否则会出现出次数为负数的键。
同时，注意到是维护一个定长的窗口，故在缩短左边界时，不需要使用while，使用if即可

from collections import Counter
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1)>len(s2):
            return False
        temp=Counter(s1)
        windows=Counter()
        left=0
        right=0
        word_len=len(s1)
        while right<len(s2):
            windows[s2[right]]+=1
            right+=1
            if right-left==word_len:
                if windows==temp:
                    return True
                left+=1
                windows[s2[left-1]]-=1
                if windows[s2[left-1]]==0:
                    del windows[s2[left-1]]
        return False

if __name__=="__main__":
    print(Solution().checkInclusion(s1 = "ab" ,s2 = "eidbaooo"))

接下来，就全是红题了（不明白为什么滑动窗口有那么多红题）

leetcode：30串联所有单词的字串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = [“ab”,”cd”,”ef”]， 那么 “abcdef”， “abefcd”，”cdabef”， “cdefab”，”efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,”bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,”foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,”bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,”bar”,”the”] 顺序排列的连接。 子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,”the”,”foo”] 顺序排列的连接。 子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,”foo”,”bar”] 顺序排列的连接。

还是用老方法分析题目，题目给出words里面的所有单词都是定长的，那么可以确定是维护一个定长的数组，同时也是判断是否为给定字符串的排列，故也可以使用python里的Couner。
然而，本题还有几个值得注意的点
如果每次只是移动一个格子，就必然需要对每一窗口进行len_word的分割来得到对应的Counter，这样会造成计算复杂度逼近O（n²）最终导致超时（别问，问就是超时爆红）。然正所谓车到山前必有路，可以看出每一个word都是定长的，我们只需要对left从0-word_len-1每一个单独讨论，随后对于每一个窗口，每次移动一个word_len，这样，就可以避免重复计算Counter了。
以下为对应代码：

from collections import Counter
class Solution(object):
    def findSubstring(self, s, words):
        """
        串联所有单词的字串
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        word_len=len(words[0])
        total_len=word_len*len(words)
        word_count=Counter(words)
        s_count=Counter()
        left=0
        right=0
        res=[]
        if total_len>len(s):
            return res
        for i in range(word_len):
            left=i
            right=i
            while right<len(s):
                s_count[s[right:right+word_len]]+=1
                right+=word_len
                if right-left==total_len:
                    if s_count==word_count:
                        res.append(left)
                    left+=word_len
                    s_count[s[left-word_len:left]]-=1
                    if s_count[s[left:left-word_len]]==0:
                        del s_count[s[left:left-word_len]]
            if s_count==word_count:
                res.append(left)
            s_count.clear()
        return res
if __name__ == '__main__':
    s="barfoothefoobarman"
    words=["foo","bar"]
    print(Solution().findSubstring(s,words))

leetcode76：最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。

示例 2：

输入：s = “a”, t = “a” 输出：“a” 解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

同样用老方法分析，有题目可得为非定长滑动窗口，同时是判断是否覆盖对应字串，故可以用python里的Counter进行判断，只要t中所有键值对都小于Counter里的即可。

from collections import Counter
class Solution(object):
    def counters_contains(self,counter1:Counter,counter2:Counter)->bool:
        """
        判断counter1是否包含counter2
        :param counter1:
        :param counter2:
        :return:
        """
        for item,count in counter2.items():
            if counter1.get(item,0)<count:
                return False
        return True
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        temp=Counter(t)
        windows=Counter()
        left=0
        right=0
        res=""
        len_t=len(t)
        if len(s)<len(t):
            return ""
        while right<len(s):
            windows[s[right]]+=1
            right+=1
            while self.counters_contains(windows,temp):
                if res=="":
                    res=s[left:right]
                else:
                    if len(res)>right-left:
                        res=s[left:right]
                windows[s[left]]-=1
                left+=1
                if windows[s[left]]==0:
                    del windows[s[left]]
        return res
if __name__=="__main__":
    s='ADOBECODEBANC'
    t='ABC'
    print(Solution().minWindow(s,t))

leetcode：632最小区间

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 输出：[20,24] 解释： 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。 列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]] 输出：[1,1]

此题需要先分析一下，再转化为滑动窗口。首先先将nums内的元素转为元组，元组分别由数组值与数组对应所在列表的索引，随后再对所有的数组进行排序，然后只看对应的列表索引，就可以转换为一个滑动窗口问题。
解析如下：
首先将 k 组数据升序合并成一组，并记录每个数字所属的组，例如：

[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

合并升序后得到：
[(0,1),(4,0),(5,2),(9,1),(10,0),(12,1),(15,0),(18,2),(20,1),(22,2),(24,0),(26,0),(30,2)]

然后只看所属组的话，那么
[1,0,2,1,0,1,0,2,1,2,0,0,2]

按组进行滑窗，保证一个窗口的组满足k组后在记录窗口的最小区间值。

[1 0 2] 2 1 0 1 0 2 1 2 0 0 2 [0, 5]
1 [0 2 1] 1 0 1 0 2 1 2 0 0 2 [0, 5]
1 0 [2 1 0] 0 1 0 2 1 2 0 0 2 [0, 5]
1 0 [2 1 0 1] 1 0 2 1 2 0 0 2 [0, 5]
1 0 [2 1 0 1 0] 0 2 1 2 0 0 2 [0, 5]
1 0 2 1 0 [1 0 2] 2 1 2 0 0 2 [0, 5]
1 0 2 1 0 1 [0 2 1] 1 2 0 0 2 [0, 5]
1 0 2 1 0 1 [0 2 1 2] 2 0 0 2 [0, 5]
1 0 2 1 0 1 0 2 [1 2 0] 0 0 2 [20, 24]
1 0 2 1 0 1 0 2 [1 2 0 0] 0 2 [20, 24]
1 0 2 1 0 1 0 2 [1 2 0 0 2] 2 [20, 24]

作者：Netcan
链接：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/solutions/240717/pai-xu-hua-chuang-by-netcan/

至此，转换为一个不定长判断是否覆盖的滑动窗口问题，判断是否覆盖，其实只用判断Counter的长度是否相等即可，因为元素是固定，即[i for i in range(len(nums))]

from collections import Counter
class Solution:
    def is_min_range(self,left,right,min_range):
        """
        判断windows区间是否为最小
        :param left:区间左边界
        :param right:区间有边界
        :param min_range:当前最小区间
        :return:
        """
        if right-left<min_range[1]-min_range[0]:
            return True
        elif right-left==min_range and left<min_range[0]:
            return True
        else:
            return False
    def smallestRange(self, nums):
        """
        求最小区间
        1，将nums合并为一个列表，列表元素为一个元组，第一个元素为数组值，第二个元素为元素归属的数组编号
        2，合并后的列表进行排序
        3，使用滑动窗口，得到最小区间
        4，返回最小区间
        :param nums:
        :return:
        """
        nums_list=[]
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                nums_list.append((nums[i][j],i))
        nums_list=sorted(nums_list,key=lambda x:x[0],reverse=False)
        left=0
        right=0
        windows=Counter()
        temp=Counter([i for i in range(len(nums))])
        min_range=(float('-inf'),float('inf'))

        while right<len(nums_list):
            windows[nums_list[right][1]]+=1
            right+=1
            while len(windows)==len(temp):
                if self.is_min_range(nums_list[left][0],nums_list[right-1][0],min_range):
                    min_range=(nums_list[left][0],nums_list[right-1][0])
                windows[nums_list[left][1]]-=1
                if windows[nums_list[left][1]]==0:
                    del windows[nums_list[left][1]]
                left+=1

        return [min_range[0],min_range[1]]

if __name__=="__main__":
    print(Solution().smallestRange([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]))

最后，进行模板总结，对于滑动窗口，可以按照规则分为定长与不定长两种类别，同时，若判断条件为是否重复，则可用set，其余一般为使用Counter，模板如下

def move_windows(s:str,t:str):
    """
    滑动窗口模板
    :param s: 
    :param t: 
    :return: 
    """
    left=0
    right=0
    if 终止条件:
        return ""
    while right<len(s):
        窗口扩大
        right+=1
        while 窗口缩小条件:  #如果为定长，则用if
            if 题目条件:
                记录所维护变量
            窗口缩小
            left+=1
            若用counter则消去值为0的键
    
    return 所维护变量