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

- 使用两个指针 `left`，`right`。`left` 指向序列第一个元素，即：`left = 0`，`right` 指向序列最后一个元素，即：`right = len(nums) - 1`。

- 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，`left += 1`。当满足另外一定条件时，将右指针左移，`right -= 1`。

- 直到两指针相撞（即 `left == right`），或者满足其他要求的特殊条件时，跳出循环体。

left = 0

right = len(nums) - 1

while left < right:

if 满足要求的特殊条件:

return 符合条件的值

elif 一定条件 1:

left += 1

elif 一定条件 2:

right -= 1

return 没找到 或 对应值

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

- 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。

- 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

下面我们根据具体例子来讲解如何使用对撞指针来解决问题。

给定一个升序排列的整数数组：`numbers` 和一个目标值 `target`。

要求：从数组中找出满足相加之和等于 `target` 的两个数，并返回两个数在数组中下的标值。

注意：数组下标从 `1` 开始计数。

这道题如果暴力遍历数组，从中找到相加之和等于 `target` 的两个数，时间复杂度为 `O(n^2)`，可以尝试一下。

class Solution:

def twoSum(self, numbers: List[int], target: int) -> List[int]:

size = len(numbers)

for i in range(size):

for j in range(i + 1, size):

if numbers[i] + numbers[j] == target:

return [i + 1, j + 1]

return [-1, -1]

结果不出意外的超时了。所以我们要想办法减少时间复杂度。

因为数组是有序的，所以我们可以考虑使用双指针来减少时间复杂度。具体做法如下：

- 使用两个指针 `left`，`right`。`left` 指向数组第一个值最小的元素位置，`right` 指向数组值最大元素位置。

- 判断两个位置上的元素的和与目标值的关系。

- 如果元素和等于目标值，则返回两个元素位置。

- 如果元素和大于目标值，则让 `right` 左移，继续检测。

- 如果元素和小于目标值，则让 `left` 右移，继续检测。

- 直到 `left` 和 `right` 移动到相同位置停止检测。

- 如果最终仍没找到，则返回 `[-1, -1]`。

class Solution:

def twoSum(self, numbers: List[int], target: int) -> List[int]:

left = 0

right = len(numbers) - 1

while left < right:

total = numbers[left] + numbers[right]

if total == target:

return [left + 1, right + 1]

elif total < target:

left += 1

else:

right -= 1

return [-1, -1]

给定一个字符串 `s`。

要求：判断是否为回文串（只考虑字符串中的字母和数字字符，并且忽略字母的大小写）。

- 回文串：正着读和反着读都一样的字符串。

使用对撞指针求解。具体步骤如下：

- 使用两个指针 `left`，`right`。`left` 指向字符串开始位置，`right` 指向字符串结束位置。

- 判断两个指针对应字符是否是字母或数字。 通过 `left` 右移、`right` 左移的方式过滤掉字母和数字以外的字符。

- 然后判断 `s[start]` 是否和 `s[end]` 相等（注意大小写）。

- 如果相等，则将 `left` 右移、`right` 左移，继续进行下一次过滤和判断。

- 如果不相等，则说明不是回文串，直接返回 `False`。

- 如果遇到 `left == right`，跳出循环，则说明该字符串是回文串，返回 `True`。

class Solution:

def isPalindrome(self, s: str) -> bool:

left = 0

right = len(s) - 1

while left < right:

if not s[left].isalnum():

left += 1

continue

if not s[right].isalnum():

right -= 1

continue

if s[left].lower() == s[right].lower():

left += 1

right -= 1

else:

return False

return True

给定 `n` 个非负整数 $a_1,a_2, ...,a_n$，每个数代表坐标中的一个点 $(i, a_i)$。在坐标内画 `n` 条垂直线，垂直线 `i` 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$。

要求：找出其中的两条垂直线，使得它们与 `x` 轴共同构成的容器可以容纳最多的水。

示例：

- 输入：`[1,8,6,2,5,4,8,3,7]`

- 输出：`49`

- 解释：图中垂直线代表输入数组 `[1,8,6,2,5,4,8,3,7]`。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 `49`。

从示例中可以看出，如果确定好左右两端的直线，容纳的水量是由 `左右两端直线中较低直线的高度 * 两端直线之间的距离 ` 所决定的。所以我们应该使得 **较低直线的高度尽可能的高**，这样才能使盛水面积尽可能的大。

可以使用双指针求解。移动较低直线所在的指针位置，从而得到不同的高度和面积，最终获取其中最大的面积。具体做法如下：

- 使用两个指针 `left`，`right`。`left` 指向数组开始位置，`right` 指向数组结束位置。

- 计算 `left` 和 `right` 所构成的面积值，同时维护更新最大面积值。

- 判断 `left` 和 `right` 的高度值大小。

- 如果 `left` 指向的直线高度比较低，则将 `left` 指针右移。

- 如果 `right` 指向的直线高度比较低，则将 `right` 指针左移。

- 如果遇到 `left == right`，跳出循环，最后返回最大的面积。

class Solution:

def maxArea(self, height: List[int]) -> int:

left = 0

right = len(height) - 1

ans = 0

while left < right:

area = min(height[left], height[right]) * (right-left)

ans = max(ans, area)

if height[left] < height[right]:

left += 1

else:

right -= 1

return ans

- 使用两个指针 `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 合适的值

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

下面我们根据具体例子来讲解如何使用快慢指针来解决问题。

给定一个有序数组 `nums`。

要求：删除数组 `nums` 中的重复元素，使每个元素只出现一次。并输出去除重复元素之后数组的长度。

注意：不能使用额外的数组空间，在原地修改数组，并在使用 $O(1)$ 额外空间的条件下完成。

因为数组是有序的，那么重复的元素一定会相邻。

删除重复元素，实际上就是将不重复的元素移到数组左侧。考虑使用双指针。具体算法如下：

1. 定义两个快慢指针 `slow`，`fast`。其中 `slow` 指向去除重复元素后的数组的末尾位置。`fast` 指向当前元素。

2. 令 `slow` 在后， `fast` 在前。令 `slow = 0`，`fast = 1`。

3. 比较 `slow` 位置上元素值和 `fast` 位置上元素值是否相等。

- 如果不相等，则将 `slow` 后移一位，将 `fast` 指向位置的元素复制到 `slow` 位置上。

4. 将 `fast` 右移 `1` 位。

- 重复上述 3 ~ 4 步，直到 `fast` 等于数组长度。

- 返回 `slow + 1` 即为新数组长度。

class Solution:

def removeDuplicates(self, nums: List[int]) -> int:

if len(nums) <= 1:

return len(nums)

slow, fast = 0, 1

while (fast < len(nums)):

if nums[slow] != nums[fast]:

slow += 1

nums[slow] = nums[fast]

fast += 1

return slow + 1

- 使用两个指针 `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

分离双指针一般用于处理有序数组合并，求交集、并集问题。下面我们根据具体例子来讲解如何使用分离双指针来解决问题。

给定两个数组 `nums1`、`nums2`。

要求：编写一个函数来计算它们的交集。重复元素只计算一次。

使用分离双指针求解，具体步骤如下：

- 对数组 `nums1`、`nums2` 先排序。

- 使用两个指针 `left_1`、`left_2`。`left_1` 指向第一个数组的第一个元素，即：`left_1 = 0`，`left_2` 指向第二个数组的第一个元素，即：`left_2 = 0`。

- 如果 `nums1[left_1]` 等于 `nums2[left_2]`，则将其加入答案数组（注意去重），并将 `left_1` 和 `left_2` 右移。

- 如果 `nums1[left_2]` 小于 `nums2[left_2]`，则将 `left_1` 右移。

- 如果 `nums1[left_2]` 大于 `nums2[left_2]`，则将 `left_2` 右移。

- 最后输出答案数组。

class Solution:

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:

nums1.sort()

nums2.sort()

left_1 = 0

left_2 = 0

res = []

while left_1 < len(nums1) and left_2 < len(nums2):

if nums1[left_1] == nums2[left_2]:

if nums1[left_1] not in res:

res.append(nums1[left_1])

left_1 += 1

left_2 += 1

elif nums1[left_1] < nums2[left_2]:

left_1 += 1

elif nums1[left_1] > nums2[left_2]:

left_2 += 1

return res

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

- 对撞指针：两个指针方向相反。适合解决查找有序数组中满足某些约束条件的一组元素问题、字符串反转问题。

- 快慢指针：两个指针方向相同。适合解决数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。

- 分离双指针：两个指针分别属于不同的数组 / 链表。适合解决有序数组合并，求交集、并集问题。

- 【博文】[双指针算法之快慢指针 (yanyusoul.com)](https://yanyusoul.com/blog/cs/algorithms_fast-slow-points/)

- 【博文】[双指针算法各类基础题型总结 - 掘金](https://juejin.cn/post/6855129006451687431)

- 【博文】[双指针 - 力扣加加 - 努力做西湖区最好的算法题解](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/two-pointers#zuo-you-duan-dian-zhi-zhen)

- 【博文】[LeetCode分类专题（四）——双指针和滑动窗口1 - iwehdio - 博客园](https://www.cnblogs.com/iwehdio/p/14434988.html)

- 【博文】[双指针算法各类基础题型总结 - 掘金](https://juejin.cn/post/6855129006451687431)