双指针模式
双指针法适合解决什么类型的问题？
- 适用: 需要在线性结构上同时维护两个位置关系的问题;
- 收益: 把需要双重循环的 O(n^2) 扫描降为一次 O(n) 扫描;
- 前提: 数组有序, 或移动某个指针时能确定地排除一部分答案;
三种双指针模式如何区分？
| 模式 | 指针起点 | 移动方式 | 典型问题 |
|---|---|---|---|
| 对撞指针 | 数组两端 | left 递增, right 递减, 直至相遇 | 有序数组求和、盛水容器、验证回文 |
| 快慢指针 | 同一侧 (如 0 与 1) | 满足条件时慢指针跟进 | 原地删除、去重、压缩 |
| 分离指针 | 分属两个数组 | 按各自当前元素推进 | 数组合并、求交集、字符串相加 |
如何选择双指针模式？
- 需要"两端夹逼"确定一个组合: 对撞指针;
- 需要原地保留或删除元素: 快慢指针;
- 需要同时扫描两个独立序列: 分离指针;
- 连续区间的滑动窗口是快慢指针的特殊形式, 见 滑动窗口模式;