[!info] related notes

• 原理与边界：滑动窗口
• 所属 MOC: 算法面试模式
• 相关题目: 无重复字符的最长子串, 滑动窗口最大值

滑动窗口模板

适用场景

• 连续子数组/子串问题
• 求最值、计数、满足条件的区间

只有窗口状态能够随端点移动增量维护、且收缩规则不会漏解时才能使用。含负数的任意子数组求和，不能直接按 sum > k 收缩。

最长合法窗口模板

下面是伪代码，not_valid 由具体题目的窗口不变量实现。它适用于“非法时收缩、合法时记录最长长度”；最短覆盖窗口要在合法时记录并继续收缩，不能照搬更新位置。

def sliding_window(s):
    left = 0
    window = {}  # or other data structure
    result = 0

    for right in range(len(s)):
        # 1. 扩大窗口
        window[s[right]] = window.get(s[right], 0) + 1

        # 2. 收缩窗口（当不满足条件时）
        while not_valid(window):
            window[s[left]] -= 1
            left += 1

        # 3. 更新结果
        result = max(result, right - left + 1)

    return result

变体

• 定长窗口：窗口大小固定，用 right - left + 1 == k 判断
• 不定长窗口：用 while 循环动态收缩
• 双指针变体：左右指针同时移动