算法学习笔记：双指针

前言： 用于记录总结刷题过程中遇到的同类型问题
双指针问题及用法总结

1. 总结

双指针常用于遍历连序性对象（如数组、链表等）时，使用两个或多个指针进行单向遍历及相应的操作。避免多层循环，降低算法的时间复杂度。

2. 常见类型和示例

2.1 快慢指针

快慢指针，常见的有速度快慢（同时出发，不同速）、位置快慢（先后出发，同速）

快慢指针

Leetcode283. 移动零

同速指针

Leetcode876. 链表的中间结点
Leetcode19. 删除链表的倒数第 N 个结点

2.2 对撞指针

定义左指针left，右指针right，从两端遍历直到两指针相遇或满足条件为止。

实例

Leetcode344. 反转字符串
557. 反转字符串中的单词 III

2.3 滑动窗口

维护一个窗口，不断滑动，然后更新答案。

1. 我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」。
2. 我们先不断地增加right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。
3. 此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left，我们都要更新一轮结果。
4. 重复第 2 和第 3 步，直到right到达字符串S的尽头。

实例

Leetcode3. 无重复字符的最长子串