一. 定义
- 双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个指针进行扫描,从而达到相应的目的。
- 两个相同方向的指针就是快慢指针,两个相反方向的是对撞指针。也有时候,为了处理多数组问题使用多个指针,称为分离指针。
- 双指针法需要注意的细节:
- 双指针的初始位置。
- 双指针的移动方法。
- 遍历的结束条件。
一般是利用某种性质,将原本朴素暴力的
**O(n^2)**
时间复杂度,降为**O(n)**
。二. 模板
1. 对撞指针
理论:
对撞指针是指在数组中,将指向最左侧的索引定义为左指针(left)
,最右侧的定义为右指针(right)
,然后从两头向中间进行数组遍历。快速排序就是典型的双指针问题。细节:
理论:
快慢指针是两个指针从同一侧开始遍历数组,将这两个指针分别定义为快指针(fast)
和慢指针(slow)
,两个指针以不同的策略移动,直到两个指针的值相等(或其他特殊条件)为止,如快指针(fast)
每次增长两个,慢指针(slow)
每次增长一个。
一般来说,快慢指针常用于判断链表等数据结构中是否有环。细节:
理论:
分离指针在两个不同的序列中,使用两个不同的指针来进行遍历。分离指针适用于双数组或者多数组问题。细节: