滑动窗口模板

last modify

• 模板

• 示例

  • 长度最小的子数组

  • 无重复字符的最长子串

  • 最小覆盖子串

• 更多问题

模板

def temp(s: Sequence):

    l = r = 0  # 初始化窗口, [l, r] 闭区间
    while r < len(s):
        ...  # 更新缓存
        while check():  # 检查条件
            ...  # 更新缓存或答案
            l += 1  # 移动左边界, 缩小窗口
        ...  # 更新缓存或答案
        r += 1  # 移动右边界, 扩大窗口

• 以上是滑动窗口的基础模板;

• 更新缓存和检查条件的先后顺序要看具体情况, 详见示例;

示例

长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

问题简述

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

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        ret = 0
        s = 0  # 记录当前窗口的和
        l, r = 0, 0
        while r < len(nums):
            s += nums[r]  # 更新缓存
            while s >= target:
                if not ret or r - l + 1 < ret:  # 更新答案
                    ret = r - l + 1
                s -= nums[l]
                l += 1
            r += 1
        
        return ret

无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        used = set()  # 记录已经出现过的字符
        ret = 0  # 记录最大长度

        l = r = 0  # 窗口边界
        while r < len(s):
            while s[r] in used:  # 出现重复字符, 滑动左边界
                # 移除最左边界的字符, 并缩小窗口
                used.remove(s[l])  # 更新缓存
                l += 1
            
            # 更新缓存和答案
            ret = max(ret, r - l + 1)
            used.add(s[r])
            r += 1  # 扩大窗口

        return ret

最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        from collections import Counter, defaultdict
        
        l, r = 0, 0

        ret = ''  # 记录答案
        need = Counter(t)  # 需要满足的每种字符数
        book = defaultdict(int)  # 记录出现过的字符数
        
        def check():  # 检验是否满足情况
            return all(book[k] >= need[k] for k in need)
        
        while r < len(s):
            book[s[r]] += 1  # 更新缓存
            while check():  # 条件检查
                if not ret or r - l < len(ret):  # 更新答案
                    ret = s[l: r + 1]
                book[s[l]] -= 1
                l += 1
            r += 1
        
        return ret

更多问题

algorithms/滑动窗口