滑动窗口
通过增量维护连续区间状态减少重复扫描，区分定长窗口、最长合法窗口与最短覆盖窗口。
#dev
#algorithm
#concept
#growing
#sliding-window
#two-pointers
[!info] related notes
滑动窗口
滑动窗口维护一个连续区间及其状态。右端扩张时加入元素，左端收缩时移除元素，从而避免为每个区间重新扫描。
为什么可以线性扫描
当左右端点都只向前移动时，每个元素最多进入、离开窗口各一次。如果状态更新和合法性检查也是 O(1)，总时间为 O(n)。代码里出现嵌套 while 不等于 O(n²)；关键是指针的总移动次数与状态维护成本。
并非所有连续区间问题都适用。必须证明丢弃某个左端点后，它不会在后续扩张中重新成为需要考虑的答案。
定长窗口
长度固定为 k：每加入一个新元素，移除已经超出窗口的旧元素。例如维护区间和、元音个数；若维护最大值，需要单调队列等额外结构。
不定长窗口
- 最长合法窗口：扩张后若不合法，收缩到合法，再记录长度。例如无重复字符子串。
- 最短覆盖窗口：扩张到满足条件后，先记录答案，再尝试收缩；收缩到不满足时继续扩张。
- 窗口计数：需要额外证明一个右端点对应哪些左端点，不能直接把最长窗口模板改成
count++。
边界与常见误判
- 对正数区间求和，扩张使和增大、收缩使和减小，因而可以据此移动端点。
- 存在负数时，上述规则不成立；例如
[2, -1]的和为 1，看到前缀和 2 就丢弃左端点会漏解。和为 k 的子数组 使用前缀和与哈希计数。 - 字符串窗口依赖字符计数等不变量，不依赖“元素为正数”。
- “连续”只是问题形态，不能仅凭这个词决定算法；不连续问题也并非只能用动态规划或回溯。
学习检查
- 为什么左右端点各移动一次的嵌套循环仍可能是 O(n)？
- 最长合法窗口与最短覆盖窗口为什么在不同位置更新答案？
- 负数如何破坏按区间和收缩窗口的判断？
参考题单
- 灵茶山艾府：滑动窗口与双指针题单
- 原引用入口：https://leetcode.cn/discuss/post/0viNMK/
题单来源为力扣讨论；原作者为灵茶山艾府，转载遵循原页面授权说明。
Digital Biome