双指针

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

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

对撞指针

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

解题

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

伪代码

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

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

return 没找到 或 找到对应值

适用范围

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

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

快慢指针

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

解题

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

伪代码

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

适用范围

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

分离双指针

两个指针分别属于不同的数组 / 链表，两个指针分别在两个数组 / 链表中移动。

解题

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

伪代码

left_1 = 0
left_2 = 0


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

使用范围

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

例题

下面数字是leetcode题号

344

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

直接交换left和right位置的数据就ok；

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s)-1
        while left <= right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

11

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

设置ans = 0
ans = max(ans,(right-left)*min(arr[left],arr[right]))

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            water = (j - i) * min(height[i], height[j])
            res = max(water, res)
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return res