双指针与滑动窗口 · HTML
数学 / 逻辑形态
维护窗口 [r-k+1,r] 的摘要 S。加入 a[r]；若窗口超长则移除 a[r-k]；长度达到 k 后查询/更新答案。
识别信号
- 明确出现 every subarray/substring of length k。
- 连续性不可打乱。
- 窗口统计可用加入/删除增量维护。
- 朴素方法会对重叠窗口重复计算大部分元素。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 长度可变的最长/最短区间 | 若长度由约束决定，需要 while 收缩的 variable window。 |
| 任意 k 个元素 | 滑窗只覆盖连续片段；组合选择不是窗口。 |
核心不变量
处理右端 r 后，摘要精确对应最近至多 k 个元素；只有窗口长度为 k 时才计入答案。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | right、隐式 left=right-k+1、窗口摘要（和、频次、匹配数）与最佳结果。 |
| Transition | 加入新右端；当已读元素超过 k 时移除离窗元素；窗口成熟后读取摘要。 |
| Frontier / order | 宽度固定的连续索引段，随 right 每轮整体右移一格。 |
Python 骨架
def max_fixed_sum(values, k):
if k <= 0 or k > len(values):
return None
window = sum(values[:k])
best = window
for right in range(k, len(values)):
window += values[right]
window -= values[right - k]
best = max(best, window)
return best
正确性思路
- 初始摘要等于第一个长度 k 窗口。
- 从前一窗口减去唯一离开的元素、加上唯一进入的元素，得到下一窗口的精确摘要。
- 循环按右端顺序覆盖所有且仅所有长度 k 窗口，因此最佳值正确。
复杂度
| Time | Space | Parameters |
|---|
| O(n) | O(1) 或 O(Σ) | n 为序列长；简单和用 O(1)，频次表需键域/窗口内不同元素数 Σ。 |
边界条件
- k=1 时每个单元素都是窗口。
- k=n 时只有一个窗口。
- k≤0 或 k>n 的返回契约要明确。
- 负数存在时 best 不能错误初始化为 0。
错误模式
| Pattern | Why it fails / fix |
|---|
| 离窗索引差一 | 新元素索引 right 对应离开索引 right-k。 |
| 未成熟窗口就更新答案 | 前 k-1 个前缀不是长度 k。 |
| 每轮重新 sum 切片 | 退化为 O(nk) 且产生额外切片。 |
选择与排除规则
- 长度明确固定：固定窗。
- 窗口摘要支持可逆 add/remove：优先增量维护。
- 若移除旧值困难但只要极值，可用 monotonic-deque。
相关模板
| Relation | Template | Boundary |
|---|
| 长度策略变体 | 可变长滑动窗口 | 长度由合法性动态决定。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最大定长窗口和为 7。 |
| Setup | 值 [2,5,-1,4]，k=2。 |
| Trace | 窗口和依次 7、4、3；每次只做一次加减。 |
Recall prompts
我的补充