双指针算法总结

双指针

常见的双指针有两种形式：对撞指针，左右指针。

对撞指针：

对撞指针一般用于顺序结构中，也称左右指针。

• 对撞指针从两端向中间移动。以个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终止条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
环），也就是：left == right （两个指针指向同一个位置）left > right （两个指针错开）

快慢指针：

快慢指针又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理数组或者环形链表非常有用。如果我们要研究的问题出现循环往复的情况时，均可考虑使快慢指针的思想。

题目：

普通双指针

283. 移动零

1089. 复写零

202. 快乐数

11. 盛最多水的容器

611. 有效三角形的个数

剑指 Offer 57. 和为s的两个数字

15. 三数之和

18. 四数之和

27. 移除元素

344. 反转字符串

剑指 Offer 05. 替换空格

151. 反转字符串中的单词

206. 反转链表

19. 删除链表的倒数第 N 个结点

面试题 02.07. 链表相交

977. 有序数组的平方

941. 有效的山脉数组

滑动串口

209. 长度最小的子数组

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

1004. 最大连续1的个数 III

1658. 将 x 减到 0 的最小操作数

904. 水果成篮

438. 找到字符串中所有字母异位词

30. 串联所有单词的子串

76. 最小覆盖子串

二分查找

704. 二分查找

35. 搜索插入位置

852. 山脉数组的峰顶索引

162. 寻找峰值

153. 寻找旋转排序数组中的最小值

剑指 Offer 53 - II. 0～n-1中缺失的数字