02数组+字符串+滑动窗口+前缀和与差分+双指针(D5_双指针)
目录
一、基本介绍
二、算法思想
三、算法模型
1. 对撞指针
2. 快慢指针
3. 滑动窗口
一、基本介绍
双指针是一种应用很广泛且基础的算法,严格来说双指针不是算法更像是一种思想。
双指针中的“指针” 不仅仅是大家所熟知的C/C++里面的地址指针,还是索引、游标。
二、算法思想
双指针是指在遍历对象时,使用两个或多个指针进行遍历及相应的操作。
大多用于数组操作,这利用了数组连序性的特点。双指针常用来降低算法的时间复杂度,因为使用
两个指针可以避免多层循环。
双指针的三个关键点
- 指针的起始位置的选取
- 指针的移动方向
- 指针的移动速度
这三个关键点是双指针算法的核心也是难点
三、算法模型
1. 对撞指针
对撞指针:左右两个指针,向中间靠拢。
2. 快慢指针
快慢指针:左右两个指针,一快一慢
3. 滑动窗口
滑动窗口:左右两个指针组成一个"窗口",右指针不断扩张,左指针按条件收缩。