滑动窗口的通用模板是什么？「求最长」和「求最短」有什么区别？

简化版

滑动窗口用两个同向指针 left、right 圈定一个窗口 [left, right]:right 不断向右扩展窗口、left 在需要时收缩,始终维护窗口内的某种状态(如字符计数)。两种题型:求最长——right 扩展,窗口不合法时收缩 left,合法时更新最大长度;求最短——right 扩展到窗口合法时,收缩 left 求最短。核心是「right 扩、left 缩、维护窗口状态」,每个元素进出窗口各一次,O(n)。

详细版

通用模板:

int slidingWindow(String s) {
    Map<Character, Integer> window = new HashMap<>();  // 窗口内状态
    int left = 0, res = 初始值;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // 1. 把 s[right] 加入窗口，更新状态
        window.merge(c, 1, Integer::sum);
        // 2. 判断是否需要收缩 left
        while (窗口需要收缩的条件) {
            char d = s.charAt(left);
            window.merge(d, -1, Integer::sum);         // 移出 s[left]
            left++;
        }
        // 3. 更新答案（求最长在这里更新，求最短在 while 内更新）
        res = 更新(res, right - left + 1);
    }
    return res;
}

两种题型的差异在于「收缩条件」和「更新答案的位置」:

题型	while 收缩条件	更新答案位置
求最长	窗口不合法时收缩	while 之后(窗口合法时)取 max
求最短	窗口合法时收缩	while 之内(收缩前每步)取 min

完整版教学

一、滑动窗口解决什么问题

滑动窗口专治**「连续子串 / 子数组」**且求「最长、最短、是否存在、计数」的问题。它的暴力解法是枚举所有子区间 O(n²)(甚至加上判断是 O(n³)),而滑动窗口利用「窗口的单调扩张/收缩」把它降到 O(n)。识别信号:题目要求「连续的一段」+「满足某条件」+「求最值/存在性」。

二、核心机制:right 扩、left 缩

窗口 [left, right] 的两个指针都只向右移动:

right 扩展:每轮把 s[right] 纳入窗口,更新窗口状态(如某字符计数 +1)。窗口变大。
left 收缩:当窗口「该收缩」时,把 s[left] 移出窗口、left++,更新状态。窗口变小。

因为 left 和 right 都单调右移、各走一遍,每个元素最多进窗口一次、出窗口一次,总操作 O(n)。这就是滑动窗口高效的根源——避免了对每个起点重新扫描。

三、求最长 vs 求最短(关键区别)

两类题的模板骨架一样,但收缩逻辑和更新时机相反,这是最容易混的地方:

① 求最长(如无重复最长子串):

目标是「窗口尽量大,但要保持合法」。
right 扩展后,只要窗口变得不合法(如出现重复字符),就 while 收缩 left 直到重新合法。
窗口合法时(while 之后)更新最大长度 max(res, right-left+1)。

② 求最短(如最小覆盖子串、长度最小子数组):

目标是「窗口尽量小,但要满足条件」。
right 扩展到窗口刚好满足条件时,进入 while,在满足条件的前提下不断收缩 left 求最短,每步更新最小长度,直到不再满足才停。

一句话记:求最长「不合法才缩、缩完更新」;求最短「合法就缩、缩时更新」。

四、窗口状态怎么维护

窗口需要一个数据结构记录内部信息,常见:

哈希表 / 数组计数:记录窗口内每个字符/数字的出现次数(字符串子串题)。
一个变量(和 / 计数):如「长度最小子数组」维护窗口内元素和;「覆盖子串」维护 valid(已满足要求的字符种类数)。
单调队列:「滑动窗口最大值」维护窗口内的单调递减队列(见栈与队列专题)。

加入 s[right] 和移出 s[left] 时,对称地更新这个状态,是滑动窗口正确的关键。

五、定长窗口 vs 变长窗口

变长窗口(上面的模板):窗口大小随条件动态变化,求最长/最短。大多数滑窗题是这类。
定长窗口:窗口大小固定为 k(如「长度为 k 的子数组最大和」)。更简单:right 到 k 后,每次 right++ 的同时 left++,窗口大小恒定,滑过一遍。

识别是定长还是变长,决定用哪种写法。

六、复杂度与要点

时间 O(n):每个元素进出窗口各一次。
空间 O(k):窗口状态(k 为字符集或窗口大小)。
要点:right 扩 left 缩、对称更新窗口状态;分清求最长(不合法才缩)还是求最短(合法就缩),更新答案的位置也相反。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：窗口状态只描述 [left,right)；右端扩张获取信息，左端收缩恢复或优化条件。

对应的状态推进是：求最长通常在窗口合法时更新，求最短通常在合法循环内先更新再收缩。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。若左右指针只前进，每个元素处理常数次，O(n)。

带数字走一遍：在长度 8 的数组上即使内层 while 多次执行，left 总共也最多前进 8 次。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	需要窗口状态可增量维护，并且移动方向具有可判定性
时间复杂度	通常 O(n)
额外空间	取决于窗口状态，常见 O(字符集或值域)
关键边界	不要机械套模板；负数和非单调条件可能让窗口无法安全丢弃左端
替代方案	不可增量维护时考虑前缀和、哈希、单调队列或二分

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“需要窗口状态可增量维护，并且移动方向具有可判定性”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写通常 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“若左右指针只前进，每个元素处理常数次，O(n)”。
误区：重复值和边界值不会改变代码。 不要机械套模板；负数和非单调条件可能让窗口无法安全丢弃左端。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“窗口状态只描述 [left,right)；右端扩张获取信息，左端收缩恢复或优化条件”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“在长度 8 的数组上即使内层 while 多次执行，left 总共也最多前进 8 次”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“不可增量维护时考虑前缀和、哈希、单调队列或二分”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

滑动窗口:同向双指针 [left,right],right 扩展、left 收缩,维护窗口状态,每元素进出各一次 O(n),解「连续子串/子数组求最值」。两类:求最长——窗口不合法才收缩、合法时(while 后)更新 max;求最短——窗口合法就收缩、收缩时(while 内)更新 min。窗口状态用哈希计数/变量和/单调队列,加入移出对称更新。定长窗口 right/left 同步移动。

简化版

详细版