labuladong的算法秘籍-读书笔记-双指针技巧秒杀七道数组题目

双指针：主要分为两类

1、左右指针 两个指针相向而行或者相背而行

2、快慢指针 两个指针同向而行，一快一慢

一、快慢指针技巧

原地修改数组

力扣23题、原地删除有序数组的重复项

使用快慢指针，快指针在面前，如果遇到不等于慢指针的数，慢指针前进一步，将快指针的值与慢指针

交换，然后继续往下走。直到数组结束，数组到慢指针所在的索引就是不重复的项

力扣83题、原地删除有序链表的重复项，解决方法同上

力扣27题、原地移除重复元素

使用快慢指针，慢指针指向索引0，快指针指向索引0，遍历数组，如果快指针所在数不等于指定数，将其值赋予慢指针所在位置，

然后慢指针先前一步。直到数组结束，返回慢指针之后的位置

力扣283题 移动零

使用快慢指针，慢指针指向索引0，快指针指向索引0，遍历数组，如果快指针所在数不等于指定数，将其与慢指针交换位置，

然后慢指针先前一步。直到数组结束。

二、滑动窗口技巧

滑动窗口框架

三、左右指针常用算法

二分查找

力扣167题 两数之和

左右指针一个指向头，一个指向尾。如果左不等于右执行判断左右所处数值相加是否为目标值。如果是，直接返回左右索引+1。

如果小于目标值，左指针左移。如果大于目标值，右指针左移。

只要数组有序，就应该想到双指针技巧

反转数组

使用左右指针，左指针为0，右指针为数组长度减一。如果左不等于右，左右位置互换，左++，右--

回文串判断

使用左右指针，左指针为0，右指针为数组长度减一。如果左不等于右。判断左右所在字符是否相等，不等返回false

力扣题5，最长回文字串

使用左右指针，从0开始遍历字符串，找到以索引为中心的回文串以及以该索引到索引加1为中心的字符串。判断哪个更大。

链表字串数组题、用双指针别犹豫

双指针家三兄弟，各个都是万人迷

快慢指针最神奇，链表操作无压力

归并排序找中点，链表成环搞判定。

左右指针最常见，左右两端相向行。

反转数组要靠它，二分搜索是弟弟。

滑动窗口老猛男，字串问题全靠它。

左右指针滑窗口，一前一后齐头进。

具体代码可以见我的知乎文章

https://zhuanlan.zhihu.com/p/601706960