【优选算法】双指针 {前后指针，对撞指针，快慢指针}_双指针三种形式

一、简单介绍

常见的双指针有三种形式：前后指针，对撞指针和快慢指针。

1. 前后指针：cur指针在前遍历数组，定位满足某要求的元素；dest指针在后跟随，与cur位置进行交换或复写操作。
   前后指针通常用于解决数组划分的问题。

2. 对撞指针：一般用于顺序结构中，也称左右指针。
   对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
   对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
   ◦ left == right （两个指针指向同一个位置）
   ◦ left > right （两个指针错开）

3. 快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
   这种方法对于处理环形链表或数组非常有用。
   其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
   快慢指针的实现方式有很多种，最常用的一种就是：
   • 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

注意：这里的指针不一定必须是指针，还可以是数组下标甚至是指向的数值

---

二、前后指针

2.1 移动零（数组划分）

• 题目链接：283.移动零
• 算法原理：
  
• 题解：283. 移动零 （前后指针，数组划分）

---

2.2 复写零（从后向前不覆盖复写）

• 题目链接：1089. 复写零

• 算法原理：
  

• 题解：1089. 复写零（前后指针，逆向复写防覆盖）

---

三、快慢指针

3.1 环形链表Ⅰ

• 题目链接：141. 环形链表

• 算法原理：

  解题思路： 定义快慢指针，慢指针一次走一个节点，快指针一次走两个节点。若快慢指针再次相遇则说明链表有环。若快指针指向了NULL则说明链表无环。
  问题深剖：

  1. 为什么快指针一定会追上慢指针？会不会正好错过呢？
     答：设慢指针入环时，快慢指针的距离为K。由于快慢指针的步长差为1，所以两者之间的距离变化如下：K,K-1,K-2,…,1,0。无论K是几，快指针都会追上慢指针，且不会错过。
  2. 快慢指针的步长可以是随机的吗？
     答：不能。由上一问可知当快慢指针的步长差为1时，快指针会追上慢指针，且不会错过。但当步长差大于1时，就可能会错过。

• 题解：141. 环形链表Ⅰ（快慢指针）

---

3.2 环形链表Ⅱ

• 题目链接：142. 环形链表 II
• 算法原理：
  1. 首先使用上一题的思路判断链表是否有环。无环直接返回NULL。
  2. 然后再寻找入环的第一个位置：
     
• 题解：142. 环形链表 II（快慢指针）

---

3.3 快乐数（出现循环往复的情况）

• 题目链接：202. 快乐数

• 算法原理：
  

• 题解：202. 快乐数 （快慢指针，环形链表）

---

四、对撞指针

4.1 盛最多水的容器（短板效应）

• 题目链接：11. 盛最多水的容器

• 算法原理：
  

• 题解：11. 盛最多水的容器 （对撞指针，木桶效应）

---

4.2 有效三角形的个数（利用单调性）

• 题目链接：611. 有效三角形的个数

• 算法原理：
  

• 题解：611. 有效三角形的个数（对撞指针，利用单调性）

---

4.3 和为s的两个数字（利用单调性）

• 题目链接：LCR 179. 查找总价格为目标值的两个商品

• 算法原理：
  

• 题解：179. 查找总价格为目标值的两个商品（对撞指针，利用单调性）

---

4.4 三数之和（利用单调性，注意处理细节）

• 题目链接：15. 三数之和

• 算法原理：
  

• 题解：15. 三数之和（对撞指针，利用单调性）

---

4.5 四数之和（利用单调性，注意处理细节）

• 题目链接：18. 四数之和

• 算法原理：
  

• 题解：18. 四数之和（对撞指针，利用单调性）