[基础算法理论] --- 双指针

1 双指针介绍

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。
如果两个指针方向相反，则称为「对撞指针」。
如果两个指针方向相同，则称为「快慢指针」。
如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

2 对撞指针

2.1 对撞指针概念

对撞指针：指的是两个指针 left，right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两个指针的值相撞（即 left==right），或者满足其他要求的特殊条件为止。
[外链图片转存中…(img-JaNwjkqS-1721614459575)]

2.2 对撞指针求解步骤

1> 使用两个指针left，right。left 指向序列第一个元素，即：left=0，right 指向序列最后一个元素，即：right=len(nums)−1。
2> 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left+=1；当满足另外一定条件时，将右指针左移，right−=1。
3> 直到两指针相撞（即left==right），或者满足其他要求的特殊条件时，跳出循环体。

2.3 对撞指针伪代码模板

left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

return 没找到 或 找到对应值

2.4 对撞指针适用范围

对撞指针一般用来解决有序数组或者字符串问题：

查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
字符串反转问题：反转字符串、回文数、颠倒二进制等问题。
下面给出具体例子来讲解如何使用对撞指针来解决问题。

3 快慢指针

3.1 快慢指针概念

快慢指针：指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为 「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。
[外链图片转存中…(img-8WZvC4ny-1721614459577)]

3.2 快慢指针求解步骤

1> 使用两个指针slow，fast。slow 一般指向序列第一个元素，即：slow = 0，fast 一般指向序列第n个元素，即：fast = n-1
。
2> 在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即 slow+=1。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即 fast+=1。
3> 到快指针移动到数组尾端（即fast==len(nums)−1），或者两指针相交，或者满足其他特殊条件时跳出循环体。

3.3 快慢指针伪代码模板

slow = 0
fast = 1
while 没有遍历完：
    if 满足要求的特殊条件:
        slow += 1
    fast += 1
return 合适的值

3.4 快慢指针适用范围

快慢指针一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。关于链表相关的双指针做法我们到链表章节再详细讲解。

下面给出具体例子来讲解如何使用快慢指针来解决问题。

4 分离指针

4.1 分离指针概念

分离双指针：两个指针分别属于不同的数组，两个指针分别在两个数组/链表中移动。
[外链图片转存中…(img-UDpuK64J-1721614459578)]

4.2 分离指针求解步骤

1> 使用两个指针left_1 ，left_2。left_1 指向第一个数组的第一个元素，即：left_1 = 0；left_2指向第二个指针的第一个数组元素，即left_2 = 0;
2> 当满足一定条件时，两个指针同时右移，即left_1 += 1、 left_2+=1;
3> 当满足另外一定条件时，将left_1指针右移，即left_1+=1;
4> 当满足其他一定条件时，将left_2指针右移，即left_2+=1;
5> 当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体。

4.3 分离双指针伪代码模板

left_1 = 0
left_2 = 0

while left_1 < len(nums1) and left_2 < len(nums2):
    if 一定条件 1:
        left_1 += 1
        left_2 += 1
    elif 一定条件 2:
        left_1 += 1
    elif 一定条件 3:
        left_2 += 1

4.4 分离双指针使用范围

分离双指针一般用于处理有序数组合并，求交集、并集问题。

下面给出具体例子来讲解如何使用分离双指针来解决问题。

5 双指针总结

双指针分为「对撞指针」、「快慢指针」、「分离双指针」。

对撞指针：两个指针方向相反。适合解决查找有序数组中满足某些约束条件的一组元素问题、字符串反转问题。
快慢指针：两个指针方向相同。适合解决数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。
分离双指针：两个指针分别属于不同的数组 / 链表。适合解决有序数组合并，求交集、并集问题。