算法总结：双指针技巧

一、概念技巧

1、双指针算法：

种类多，比较泛，没有很强的既定框架！
双指针（two points）通过设置两个指针不断移动来解决问题的，一般主要用来操作数组，链表以及字符串。

2、双指针的种类比较多：

1.相向双指针，两个指针从两边往中间移，也被称为对撞指针/左右端点指针。
2.背向双指针，两个指针从中间往两边移。
3.同向双指针，两个指针同时往一个方向移，
    比较典型的就是快慢指针，一个指针每次移动的步数多，另一个指针每次移动的步数少。

   区间指针：滑动窗口（也属于同向双指针）；

4.还有如果两个指针分别属于不同的数组或链表，也称为分离双指针。

3、双指针针对的问题场景

双指针技巧主要分为两类，一类是快慢指针，一类是左右指针。

快慢指针：主要解决链表中的问题，比如典型的判定链表中是否包含环、反转链表、找链表的中间节点、删除链表的倒数第 N 个结点；也用来解决数组中的问题，如移动/移除元素、删除有序数组中的重复项。

左右指针：主要解决数组（或者字符串）中的问题，比如二分查找，滑动窗口。

4、举例分析解题思想

1、先分类；2、判定当前分类使用的“算法技巧”

具体：
283.移动零=》
解题思想：
1、先分类
属于【数组划分、数组分块】
2、当前分类使用的“算法技巧”
算法技巧：同向双指针（一前一后）

1089.复写零
解题思想：
1、先分类
属于【数组划分、数组分块】
2、当前分类使用的“算法技巧”
算法技巧：同向双指针（一前一后）
通过双指针来变成就地修改

202.快乐数
解题思想：
1、先分类
属于【环形链表】
2、当前分类使用的“算法技巧”
算法技巧：快慢指针

11.快乐数
解题思想：
1、先分类
属于【环形链表】
2、当前分类使用的“算法技巧”
算法技巧：对撞指针

二、具体说明

1、常见类型

1.快慢指针
2.左右端点指针（相向双指针）
3.区间指针 - 滑动窗口（同向双指针）

2、经典例题

2.1、快慢指针
（1）链表判环
141. 环形链表；
142. 环形链表 II；
287. 寻找重复数
876. 链表的中间结点

（2）读写指针
26. 删除有序数组中的重复项 - 仅保留一次
80. 删除有序数组中的重复项 II - 保留两次重复
递推：删除且保留k次重复
202. 快乐数

2.2、左右端点指针（相向双指针）
（1.1）二分法
34. 在排序数组中查找元素的第一个和最后一个位置
33. 搜索旋转排序数组 - （非有序序列）
162. 寻找峰值 - （非有序序列）
475. 供暖器 （使用python库 bisect）

（1.2）二分答案
购物系统的降级策略
875. 爱吃香蕉的珂珂
组装最大可靠性设备
最佳植树距离
食堂供餐
数据最节约的备份方法 - 二分答案+dfs

（2）有序数组暴力枚举 - N数和问题
167. 两数之和 II - 输入有序数组
1. 两数之和
15. 三数之和
18. 四数之和
递推：N数之和
16. 最接近的三数之和
881. 救生艇

（3）其他暴力枚举
75. 颜色分类 - 类似于荷兰国旗问题
977. 有序数组的平方
11. 盛最多水的容器
42. 接雨水

2.3、区间指针 - 滑动窗口 （同向双指针）
（1）定长滑动窗口
1456. 定长子串中元音的最大数目
剑指 Offer 22. 链表中倒数第k个节点

（2）变长滑动窗口
1004. 最大连续1的个数 III
209. 长度最小的子数组 - （从符合条件到不符合条件）
713. 乘积小于 K 的子数组 - （从不符合条件到符合条件）
3. 无重复字符的最长子串 - 只增不减

2.4、其他类型指针
（1）中间开花
5. 最长回文子串
（2）快慢指针变体
392. 判断子序列
（3）从尾向头逆序
88. 合并两个有序数组