一. 定义

  • 双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针进行扫描，从而达到相应的目的。
  • 两个相同方向的指针就是快慢指针，两个相反方向的是对撞指针。也有时候，为了处理多数组问题使用多个指针，称为分离指针。
  • 双指针法需要注意的细节：
    1. 双指针的初始位置。
    2. 双指针的移动方法。
    3. 遍历的结束条件。

  • 一般是利用某种性质，将原本朴素暴力的**O(n^2)**时间复杂度，降为**O(n)**。

    二. 模板

    1. 对撞指针

  • 理论：
    对撞指针是指在数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。快速排序就是典型的双指针问题。

  • 细节：

    1. 双指针的初始位置
      左指针（left)一般指向数组的第一个元素。
      右指针（right)一般指向数组的第一个元素。
    2. 双指针的移动方法
      左指针(left）向右边👉移动，一般每次移动一个位置。
      右指针(right）向左边👈移动，一般每次移动一个位置。
    3. 遍历的结束条件
      左指针（left）位置和右指针（right）位置逆序。开始的时候，right >= left，因此结束的条件就是 right < left。

      2. 快慢指针

  • 理论：
    快慢指针是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如快指针（fast）每次增长两个，慢指针（slow）每次增长一个。
    一般来说，快慢指针常用于判断链表等数据结构中是否有环。

  • 细节：

    1. 双指针的初始位置
      左指针（left)一般指向数组的第一个元素。
      右指针（right)一般指向数组的最后一个元素。
    2. 双指针的移动方法
      左指针(left）向右边👉移动，一般每次移动一个位置。
      右指针(right）向右边👉移动，一般每次移动两个位置。
    3. 遍历的结束条件
      慢指针（slow）位置和快指针（fast）位置重合；快指针（fast）达到数组的最后一个元素。
    4. 特别注意
      要判断达到最后一个元素。否则会出现死循环。

      3. 分离指针

  • 理论：
    分离指针在两个不同的序列中，使用两个不同的指针来进行遍历。分离指针适用于双数组或者多数组问题。

  • 细节：

    1. 双指针的初始位置
      第n个指针（n）一般指向第n个数组的第一个元素。
    2. 双指针的移动方法
      指针（n）一般向右边👉移动，一般每次移动一个位置。
    3. 遍历的结束条件
      有一个指针（n）到达序列末端，停止遍历。

      三. 经典题目

      1. 对撞指针

2. 快慢指针

3. 分离指针