双指针

快慢指针

快慢指针是一种在线性数据结构上使用两个不同速度指针的技术。

特点

1. 时间复杂度：
2. 空间复杂度：
3. 适用于环形检测、中点查找等场景

分类

对撞指针

对撞指针是一种在有序数组中使用两个相向移动的指针的技术。

特点

1. 时间复杂度：
2. 空间复杂度：
3. 适用于查找、排序等场景

分类

滑动窗口

滑动窗口是一种使用两个指针维护一个区间的技术。

特点

1. 时间复杂度：
2. 空间复杂度：与具体问题相关
3. 适用于子串、子数组问题

分类

应用场景对比

快慢指针适合：

1. 链表环形检测
2. 链表中点查找
3. 链表倒数第k个
4. 链表相交判断

对撞指针适合：

1. 有序数组查找
2. 数组元素对撞
3. 区间和问题
4. 回文串判断

滑动窗口适合：

1. 子串问题
2. 子数组问题
3. 区间统计
4. 连续序列维护

选择建议

1. 链表问题优先考虑快慢指针
2. 有序数组优先考虑对撞指针
3. 子串/子数组优先考虑滑动窗口
4. 需要常数空间时考虑双指针
5. 需要线性时间时考虑双指针