双指针算法

发表于 分类于 ， 阅读次数：
双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。其操作对象为一个或多个序列，作用通常为化二维为一维，即将 $O(n^2)$ 的时间复杂度优化到 $O(n)$ 级别。

双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。其操作对象为一个或多个序列，作用通常为化二维为一维，即将 $O(n^2)$ 的时间复杂度优化到 $O(n)$ 级别。其代码通常(?)如下所示：

1
2
3
4
5
for (int i = 1, j = 1; i <= n; i++)
{
    while (j < i && check(i, j)) j++;
    // 每道题目的具体逻辑
}

我们可以根据具体的应用场景将双指针分为以下三类：

1. 对撞指针

对于一个序列，对撞指针指的是将一个指针放置在序列左侧，一个指针放置在序列右侧，然后将两个指针同时向中间移动。当发现不满足性质的元素时，单侧指针停止；当双侧指针同时停止时，则交换两个指针指向的元素。这样，该序列就又重新满足了所要求的性质，两个指针都又可以继续移动。

e.g 给定一个字符串，反转该字符串中的元音字母，如：hello -> holle

解：对于给定的字符串，我们分别在左右各放置一个指针，令其向中间移动，且所指元素为元音字母时停止。当同时停止时，交换两元素。这样就实现了字符串元音字母的反转。

同样，对撞指针还是快速排序一种优秀写法的实现基础。具体内容见排序算法的博客。

2.快慢指针

快慢指针更多地在链表中使用。对于一个序列，我们在起始端设置一快一慢两个指针，让他们同时开始移动。通过使其满足特殊的状态，我们就可以从中得知链表的一些性质。比如：

  • 判断链表的中点（快指针速度二倍）
  • 判断链表中有无环（龟兔赛跑求是否有相遇点）

另外，归并排序其实也算是一种快慢指针，只不过其针对的是两个序列，快慢的衡量变为了序列元素的大小本身。

3.滑动窗口

这个名不知道是谁起的，不过和某单调队列经典题应该没啥关系。

滑动窗口，顾名思义，就是一个滑动的窗口。其抽象意义体现为：对于一左一右两个指针，它们同时移动，并且之间具有一定的距离。其中，窗口中的内容需要在序列中满足一定的性质，双指针也就是用来维护该内容。这样说起来的确很抽象，不过滑动窗口最经典的应用应该就是 kmp 。

在 kmp 问题中，next 数组实际上就保存了该段序列的最小重复单元——窗口的长度 (n - next[n]) 就是最小重复单元的长度。这样就通过双指针保存下了最小重复单元。该部分内容详见 kmp 问题的博客。