直接回答:通用模板:右指针扩张纳入元素更新窗口状态,左指针收缩直到窗口重新满足约束,每步按题意更新答案——双指针均只前进,O(n)。区分两类:定长窗口(长度 k 固定,右进一格左出一格,求窗口内的最值/和/异位词判定);变长窗口(求满足约束的最长/最短子串——“最长”在收缩前更新答案,“最短”在收缩过程中更新)。

展开解析:题感三分类:求“最长满足条件的子串”(无重复字符的最长子串、至多 K 个替换的最长重复子串、至多含两类字符的水果篮)——窗口违规才收缩,收缩到合法为止,扩张后更新最长值;求“最短满足条件的子串”(最小覆盖子串、长度最小的子数组和 ≥ target)——窗口一旦满足就持续收缩并沿途更新最短值,直到不再满足;计数型(恰好 K 个不同字符的子串数)——用“至多 K”减“至多 K-1”的技巧转化,因为“恰好”不可单调收缩而“至多”可以,这是计数型的万能钥匙。状态维护细节:字符频次用定长数组或哈希表,配一个“有效计数器”(如匹配种数)避免每次扫全表判定——判定 O(1) 是滑动窗口保持线性的关键。与单调队列的协同:定长窗口求最值(滑动窗口最大值)窗口内最值维护要单调队列,前缀和场景窗口和最值用单调队列维护前缀和下标(和至少为 K 的最短子数组)。复杂度论证一句话:左右指针各走 n 步,窗口内操作均摊 O(1),总 O(n)。常见错误:收缩条件写成 if 而不是 while(一次收缩不够)、计数型忘记“至多减至多”转化硬做“恰好”。

追问方向:为什么“恰好 K”不能直接滑窗而“至多 K”可以?最小覆盖子串的匹配计数器怎么设计?

(约 490 字)