what？

一般用于获取数组中“满足某条件C”的最长/短/等于某长度的区间。滑动窗口算法维护两个指针l,r，利用lr寻找满足条件C的区间[l,r)。lr移动方向相同，形成了一个「窗口」在直线上「滑动」的效果。

when？

满足什么条件可以使用滑动窗口？

如果区间的寻找问题能化为 “有一个条件C（一般都为题目要求的条件），当满足C（不满足C）时，对区间的操作应为l右移；当不满足C（满足C）时，对区间的操作应为r右移”，则可用滑动窗口。
即可以根据条件C可将当前行动分为 r右移 or l右移二者中的一个

if 满足条件C（or不满足条件C）:
    应进行的操作 = l右移
else:
    应进行的操作 = r右移

为什么满足这个条件就可以使用滑动窗口？

• 不妨将C与C的反面分别是满足l右移条件与满足r右移条件，显然这两个条件互补。由于二者互补，满足l右移条件时必然不满足r右移条件，不能r右移必须l右移；反之亦然。也就是说，能l右移时必然不能r右移；能r右移时必然不能l右移。这是可使用滑窗的关键。
  • e.g. lc3 若当前区间不包含重复的元素->右移r；若当前区间包含重复元素->右移l
  • e.g. lc67 若当前区间覆盖了所有t元素->右移l；反之->右移r

什么问题满足这种条件？

• 一般而言，这种“l能右则r不能右，r能右则l不能右”的性质是由"最长\短"和“要求C”共同作用导致的。
  将 要求C 和 最长/短 看作两个平等的要求，这两个要求 一个希望l越右越好 r越左越好；一个希望l越左越好 r越右越好。可以发现这两个要求的希望是矛盾的，由于要同时满足这两个条件，导致我们不能直接把两个指针一个放最左一个放最右。
  但正是这种矛盾的性质使得问题满足“l能右则r不能右，r能右则l不能右”。以具体问题为例：

  • e.g. lc3
    • “不包含重复字符”希望l越右越好，r越左越好（极限情况：l右到数组结束，区间啥都不包括，必然是满足要求的）；“最长”要求l越左越好，r越右越好（这个很好理解了，l越左r越右，区间越长）。
    • 那么在区间满足“不包含重复字符”时，为了满足“最长”，应进行的操作“r能右l不能右”；在区间“包含重复字符”时，为了满足“不包含”，应进行的操作“l能右r不能右”
  • e.g. lc76
    • “包含t所有字符”要求l越左越好，r越右越好（极限情况：包含所有的元素了，必然是最可能满足要求的）；“最短”要求l约右越好，r越左越好（极限情况：空区间，最短）
    • 那么在区间满足“包含t所有字符”时，为了满足最短，应进行的操作“l能右r不能右”；在区间不满足“包含t所有字符”时，为了满足“包含”，应进行的操作“r能右l不能右”

• 以上分析的是“最长/短”的要求。采用滑动窗口如上所述，是很自然的。对于要求等于某长度的，可以在长度变化的过程中进行判断，看何时长度等于要求值，具体见后。（e.g. lc438 lc567）

how？

模板

l, r = 0, 0 #初始化为0，当前区间[l, r)为空，区间长度始终为 r-l
while r < len(s): # 保证r不出界
    ... # 对状态做修改（上一个轮执行了r右移，状态改变了），好让程序在后面检测是否满足条件
    r += 1 # 利用大循环完成r指针右移，这一步其实放在小循环结束后也可以，影响不大，注意长度计算、数组索引取对就行
    while 使得l右移的条件，也是使得r右移条件的反 and l < r: # 注意这里刚经过 r += 1，也就是说刚遍历过元素为 s[r-1]，而不是 s[r]. 这里可能会需要l < r
        min_len = min(min_len, r-l) # 最小值
        ... # 对状态做修改（上一轮小循环执行了l右移，状态改变了），好让程序在后面检测是否满足条件
        l += 1 # 利用小循环完成l指针右移
    max_len = max(max_len, r-l) # 最大值

分析

• recall：

  • 当问题满足能l右移时必然不能r右移；能r右移时必然不能l右移时可采用滑动窗口。（从when中分析来的核心）
  • r指针用于扩张窗口，l指针用于收缩窗口。注意：这个区间是单调向右移动的。
  • 由于最长/短+条件C的共同作用，导致当r指向任意元素时，必然有唯一符合这两个条件的区间（称作“唯一性”，很重要！！）【ps：当然l指向每个元素时必然也只有唯一符合条件的区间，只不过这里我们不用这一条性质】

• 由于“唯一性”，那么我们要做的就是用r遍历所有元素（这样可以找到所有符合要求的区间），对于r指向的每个位置找到符合要求的区间（满足要求C，这里先不管长度的要求），然后比较这些区间的长度，获得最长/短（在这里处理对长度的要求）。

• 整个程序采用大小两个while循环，任务分别为：

  • 大循环while：当r<len(s)时大循环while不断右移r，以扩张区间；——用r遍历所有元素
  • 小循环while：当r右移后区间不满足条件时采用小循环右移l使得其满足条件C；——对于r指向的每个位置找到符合要求的区间

• 根据两个循环的任务，写法如下：

  • 利用大循环完成r右移r+=1，利用小循环完成l右移l+=1。（因为r用于扩张，所以必然先执行r右移，采用大循环。）
  • 大循环控制r小于len(s)，小循环写使得l右移的条件 and l小于r（理论上这里需要控制l小于r，但是’l小于r’有时必然满足，这里忽略掉了，但写了肯定是没错的）
    • 小循环的控制条件具体是满足题目要求or不满足题目要求并不重要，关键是使得l右移。
    • 当求最短区间时，l右移的条件=C；当求最长区间时，l右移的条件=C的反
      why？假设求最长区间时，l右移条件=C，也就是说C希望l约右越好，而最短也希望l越右越好。显然不可能，这也不符合when中的分析。（这一点不用记，小循环条件直接分析啥时候l右移就行了，别管题目的要求C是啥都无所谓。）
    • 关于小循环写l右移条件的合理性分析：
      1）while结束后：进入大循环while进行r右移，这是科学的。因为此时不满足l右移的条件，则必然满足r右移的条件，应该进行r右移。
      2）进入while前：在大循环看，每次r右移后都会判断是否满足l右移，若满足则进入此循环进行l右移（此时必然不满足r右移条件，应该l右移）；若不满足l右移则进入下一轮大循环继续进行r右移（此时不满足l右移条件，应该l右移），这也是科学的。
      以上两点都是由“l能右则r不能右，r能右则l不能右”这一性质保证的。也正是因为这一点，才能采用这种大小循环的结构。

• 一般题目都会要求区间最长or最短（recall：当求最短区间时，l右移的条件=C；当求最长区间时，l右移的条件=C的反）

  • 关于区间长度
    • 始终维护[l,r)为所找区间，所以区间长度始终为r-l
    • 当然也可以维护cur_len变量来记录长度，每次r右移+1，l右移-1，但是没有r-l简洁明白
  • 对比更新获得最大值地方：在大循环的末尾进行
    • why？刚退出小循环（区间不满足小循环条件+小循环条件为C的反），也就是说此时区间满足C。[l, r)是符合要求的。大循环是遍历r，取得所有满足C的区间（注意：经过小循环已经通过l右移使得当前[l,r)区间满足C了），所以在大循环每轮的末尾进行对比更新一下。
  • 对比更新获得最小值地方：在小循环的刚开始
    • 首先要解释为什么不在大循环的末尾进行（即对比更新获得最大值的地方）：刚退出小循环（区间不满足小循环条件+小循环条件为C），也就是说此时区间[l,r)是不满足C的，当然不能在这里比较更新。那么应该在哪里呢？
    • 注意，小循环的条件是C，也就是说每次循环内部[l,r)都是符合C的，而小循环右移l每次都使得区间变短，那么每次在小循环里（l右移前）进行对比更新也就合理了。

• 小循环用于右移l收缩区间，除了获得最小值外，对于每次收缩结束都想要进行的操作也应该在小循环内部完成：

  • e.g. 保证区间长度不小于某一值以获得某固定长度的区间（lc438 lc567）

• 对于求最短长度的问题，一般将minLen设置成某最大值，但是不像求最长区间可以直接返回maxLen。最短长度的问题需要先判断下minLen是否=最开始设定的最大值（此时说明符合条件的区间不存在）再返回。

例子

看懂上述分析后，你就可以去秒杀lc上滑动窗口的题啦。

lc3：无重复字符的最长子串

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

• 不变量：[left, right) 内不包含重复字符。
• 当“不包含重复字符”时，r右移；当“含重复字符”时，l右移

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l, r = 0, 0
        cur_len, max_len = 0, 0
        from collections import Counter
        cnt = Counter()

        while r < len(s):
            cnt[s[r]] += 1
            r += 1
            while cnt[s[r-1]] > 1:
                cnt[s[l]] -= 1
                l += 1
            max_len = max(max_len, r-l)
        return max_len

lc76：最小覆盖字串

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

• 不变量：[l,r)覆盖t所有元素
• 当“包含t所有元素”时，l右移；当“不包含”时，r右移

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l, r = 0, 0
        start, min_len = 0, len(s)+1
        from collections import Counter
        cnt = Counter(t)

        def contain_all_t(cnt):
            for itm in cnt.values():
                if itm > 0: return False
            return True

        while r < len(s):
            if s[r] in cnt.keys(): cnt[s[r]] -= 1
            r += 1

            while contain_all_t(cnt):
                if min_len > r-l:
                    min_len = r - l
                    start = l
                if s[l] in cnt.keys(): cnt[s[l]] += 1
                l += 1
        # print(start, min_len)
        if min_len == len(s) + 1: return ''
        else: return s[start:start+min_len]

lc209：长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

• 当“和小于target时，r右移；当和大于等于target时，l右移”

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l, r, cur_sum, lenght = 0, 0, 0, len(nums)
        min_len = lenght + 1
        while r < lenght:
            cur_sum += nums[r]
            r += 1
            while cur_sum >= target:
                min_len = min(min_len, r - l)
                cur_sum -= nums[l]
                l += 1
        if min_len == lenght + 1: return 0
        else: return min_len

lc438：找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

• 当区间内频数大于等于p的频数时，l右移；当频数小于p的频数时，r右移

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        from collections import Counter
        def is_morethan_p(cnt): # 
            is_all_zeors = True
            for itm in cnt.values():
                if itm > 0: return -1
                elif itm < 0: is_all_zeors = False
            if is_all_zeors: return 0
            else: return 1
        cnt = Counter(p)
        res = set()
        l, r = 0, 0
        length, len_p = len(s), len(p)
        while r < length:
            if s[r] in cnt: cnt[s[r]] -= 1
            r += 1
            while is_morethan_p(cnt) >= 0 and l < r:
                if is_morethan_p(cnt) == 0 and r-l == len_p: res.add(l)
                if s[l] in cnt: cnt[s[l]] += 1
                l += 1
            # print('out',end=' ')
            # print(s[l:r])
        return list(res)

lc424：替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

• 当区间内非最多元素频数之和小于等于k时，r右移；当大于k时，l右移

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:

        def how_many(cnt):
            # print(cnt, end = ' ')
            # print(sum(cnt.values()), cnt.most_common(1)[0][-1])
            return sum(cnt.values()) - cnt.most_common(1)[0][-1]

        from collections import Counter
        cnt = Counter()
        l, r, length = 0, 0, len(s)
        max_len = 0
        while r < length:
            cnt[s[r]] += 1
            r += 1
            while how_many(cnt) > k and l < r:
                cnt[s[l]] -= 1
                l += 1
            max_len = max(max_len, r - l)
        return max_len

lc567： 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。

• 当包含s1中所有元素，即频数大于等于s1频数时，l右移；当小于时，r右移

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        len_s1, len_s2 = len(s1), len(s2)
        l, r = 0, 0
        cnt = Counter(s1)

        while r < len_s2:
            if s2[r] in cnt: cnt[s2[r]] -= 1
            r += 1
            while all([itm <= 0 for itm in cnt.values()]):
                if r - l == len_s1: return True
                if s2[l] in cnt: cnt[s2[l]] += 1
                l += 1
        return False

以上就是滑动窗口的全部内容了，有任何疑问欢迎留言！