双指针与滑动窗口 · HTML
数学 / 逻辑形态
循环前 [0,write) 已是处理 read 之前元素所得的正确输出。检查 a[read] 后，可选择写入 a[write] 并递增 write。
识别信号
- 要求 in-place 删除、去重或移动。
- 输出是输入元素的稳定子序列。
- 一个指针读新数据，另一个指向下一个写位置。
- 答案长度可能小于输入长度，尾部内容无需关心。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 连续窗口约束 | 若 left 表示窗口左端且会反复收缩，应使用滑窗语义。 |
| 需要任意重排 | 若稳定性不要求，可与末尾交换；读写模板不是唯一最佳方案。 |
核心不变量
处理 a[0:read] 后，a[0:write] 恰是它们按规则保留的正确、稳定输出，且 write≤read+1。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | read、write、当前元素以及判断是否保留所需的少量摘要。 |
| Transition | read 每轮前进；若当前元素应保留，写到 a[write] 并令 write+=1。 |
| Frontier / order | [0,write) 为已完成输出，[write,read) 为可覆盖区，[read,n) 为未读输入。 |
Python 骨架
def stable_filter(values, keep):
write = 0
for read, value in enumerate(values):
if keep(value):
values[write] = value
write += 1
return write # valid output is values[:write]
正确性思路
- 初始空前缀正确。
- 每轮若丢弃元素，正确输出不变；若保留，把它追加到 write 恰维持稳定顺序。
- 归纳至 read=n 后，前缀包含且只包含所有应保留元素，write 即长度。
复杂度
| Time | Space | Parameters |
|---|
| O(n) | O(1) | n 为输入长度；每个元素读一次，最多写一次。 |
边界条件
- 空输入返回 0。
- 全部保留时 read/write 可重合。
- 全部删除时 write 始终为 0。
- keep 若依赖上个保留元素，应读取 values[write-1] 而非上个 read。
错误模式
| Pattern | Why it fails / fix |
|---|
| 返回原数组而不返回长度 | 尾部是未定义旧值；有效区仅为 [:write]。 |
| write 无条件递增 | 会留下本应删除的空洞。 |
| 覆盖后还读取被覆盖区 | 必须保证 read 不落后于 write，且摘要引用正确前缀。 |
选择与排除规则
- 输出是稳定过滤后的子序列：读写指针。
- 允许破坏顺序且删除很少：与尾部交换可能减少写入。
- 链表没有随机写位置：改用 linked-list-rewire。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | write=3，有效前缀为 [4,6,8]。 |
| Setup | 原地保留 [4,1,6,3,8] 中的偶数。 |
| Trace | read 扫描；4 写到 0，6 写到 1，8 写到 2。 |
Recall prompts
我的补充