双指针与滑动窗口 · HTML
数学 / 逻辑形态
每个 right 加入一次；当窗口违反（最长问题）或已满足且需最短化时，用 while 移动 left 并移除状态。两个指针均单调前进。
识别信号
- 答案必须是连续子数组/子串。
- 约束可用频次、种类数、非负和等增量维护。
- 右端扩张对合法性的影响具有单向性，左移能恢复或压缩。
- 目标是 longest valid 或 shortest covering interval。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 含任意负数的和约束 | 右扩可能减小和、左缩也可能增大和，单调性失效；考虑前缀状态或单调队列。 |
| 非连续子序列 | 窗口不能跳过中间元素。 |
核心不变量
left 与 right 从不后退；在记录答案的时刻，窗口状态与 [left,right] 精确一致，并满足该变体规定的合法/最小条件。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | left、right、窗口频次/总和/缺失数，以及 best；必须定义 add/remove 对称操作。 |
| Transition | 加入 right；按目标用 while 移除 left 直到恢复合法或无法继续缩；在正确时机更新答案。 |
| Frontier / order | 所有以当前 right 结尾的候选窗口中，被单调性压缩为一个关键 left 边界。 |
Python 骨架
def longest_at_most_k_distinct(values, k):
if k < 0:
return 0
count, left, best = {}, 0, 0
for right, value in enumerate(values):
count[value] = count.get(value, 0) + 1
while len(count) > k:
old = values[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
best = max(best, right - left + 1)
return best
正确性思路
- 窗口频次通过 add/remove 与实际区间保持一致。
- 当 distinct>k，任何更小 left 的窗口也不合法，故收缩不会丢失合法最优。
- 恢复合法后当前 left 是该 right 下最靠左的合法边界，所以记录其长度覆盖最优候选。
复杂度
| Time | Space | Parameters |
|---|
| O(n) | O(Σ) | 每元素至多被 right 加入一次、被 left 移除一次；Σ 为窗口内不同键数。 |
边界条件
- 空输入返回 0 或无窗口约定。
- k=0 时只有空窗口合法。
- 删除频次到 0 时必须移除键，否则 distinct 错。
- 最短覆盖型的答案更新时机在收缩循环内，与最长型不同。
错误模式
| Pattern | Why it fails / fix |
|---|
| 用 if 代替 while | 一次左移可能仍不合法，必须持续收缩。 |
| 把所有窗口问题硬套滑窗 | 先证明指针单调性，尤其警惕负数和非单调谓词。 |
| 更新答案时机错误 | 最长合法在恢复合法后更新；最短满足通常在仍满足时边缩边更新。 |
选择与排除规则
- 连续 + 可增量 + left 单调恢复约束：滑窗。
- 求最长合法：违规时收缩，合法后记录。
- 求最短覆盖：满足时记录并继续收缩，直到不满足。
相关模板
| Relation | Template | Boundary |
|---|
| 同为左右边界 | 相向双指针 | 区别在于滑窗维护连续区间属性。 |
| 同向但语义不同 | 同向双指针 / 读写指针 | left 维护合法连续窗口而非输出前缀。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最长合法窗口长度为 3。 |
| Setup | 序列 [a,b,a,c,c]，最多 2 种值。 |
| Trace | 到 c 时窗口 a,b,a,c 有 3 种，left 连续右移到 b 被删除；随后可扩到 c,c。 |
Recall prompts
我的补充