双指针——对撞指针与左右指针

双指针——对撞指针与快慢指针

常见的双指针有两种形式，⼀种是对撞指针，一种是快慢指针。

1、对撞指针：

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

• 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。

• 对撞指针的终止条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

  • left == right （两个指针指向同⼀个位置）
  • left > right （两个指针错开）

2、快慢指针：

快慢指针又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种方法对于处理环形链表或数组非常有用。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种，最常用的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，而快的指针往后移动两位，实现⼀快⼀慢。

本篇为知识点讲解，下一篇会出有关双指针的例题来给大家讲解双指针的妙处，感觉不错的友友们可以一键三连支持一下笔者，有任何问题欢迎在评论区留言哦~