双指针

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

在数组的区间问题上，暴力算法的时间复杂度往往是 O($n^2$)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。

1. 对撞指针

> [!notice] 对撞指针： > 指的是两个指针 left、right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两个指针的值相撞（即 left == right），或者满足其他要求的特殊条件为止。

对撞指针求解步骤

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

对撞指针伪代码模板

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

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

return 没找到 或 找到对应值

对撞指针适用范围

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

• 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
• 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

力扣题目

• 11. 盛最多水的容器 - 力扣（LeetCode）
• 125. 验证回文串 - 力扣（LeetCode）
• 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

3. 快慢指针

> [!notice] 快慢指针： > 指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为 「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。

快慢指针求解步骤

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

快慢指针伪代码模板

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

快慢指针适用范围

快慢指针一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。

• 26. 删除有序数组中的重复项 - 力扣（LeetCode）

分离双指针

> [!notice] 分离双指针： > 两个指针分别属于不同的数组，两个指针分别在两个数组中移动。

分离双指针

分离双指针求解步骤

1. 使用两个指针 left1、left2。left1 指向第一个数组的第一个元素，即：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. 当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体。

分离双指针伪代码模板

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

分离双指针使用范围

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

• 349. 两个数组的交集 - 力扣（LeetCode）

双指针总结

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

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