最近刷了几个“用双指针解决”的题,比如移动零、移除指定元素、去重、模拟退格等,发现虽然写法不同,但它们本质上是在做同一件事:在原数组中筛选出想要保留的元素。
这类题其实可以统一抽象为“原地筛选模型”,而所谓的“快慢指针”就是这种模型的具体实现方式。
一,为什么用快慢指针能解决这类问题?
从“目的”出发我们会发现,这类题目:
不允许用额外空间(只能在原数组上修改);
需要压缩/过滤掉不合法的值;
希望顺序保留原始的合法值。
所以:
fast 是扫描者,遍历全部原始值;
slow 是写入者,维护“有效区间”的末尾;
每次合法就复制,非法就跳过;
最终 [0, slow) 就是结果区间。
二,如何快速识别这类题?
看到下面这些关键词你就可以考虑这个模型:
“原地”操作
“删除/移除 某些元素”
“压缩数组/去重”
“不能使用额外数组”
“返回剩下的元素(或者长度)”
三,这些题看起来不同,其实是一类问题