Description

双指针一般是指用两个（或者多个）变量在线性结构上遍历而解决的问题。 它包含两种形式：

  • 两个指针分别指向不同的序列。比如：归并排序的合并过程。
  • 两个指针指向同一个序列。比如：快速排序的划分过程。

一般更多使用、也更难想到的是第2种情况。基于同一序列还有以下几种形式：

  • 快慢指针：一快一慢，步长一大一小。例如，是否有环问题（看慢指针是否能追上快指针），单链表找中间节点问题（快指针到单链表结尾，慢指针到一半）；
  • 对撞指针：一左一右向中间逼近；
  • 滑动窗口：一般是右端向右扩充，达到停止条件后右端不动，左端向右端逼近，逼近达到停止条件后，左端不动，右端继续扩充。

双指针算法是基于暴力解法的优化，双指针算法最核心的用途就是优化时间复杂度，通常可以将时间复杂度从 O(n^2) 降低到 O(n)。
原本两个指针是有n^2种组合，因此时间复杂度是O(n^2)，而双指针算法就是运用单调性使得指针只能单向移动，因此总的时间复杂度只有
2n，降低到O(n)。之所以双指针可以O(n)实现的时间复杂度是因为指针只能单向移动，没有指针的回溯，而且每一步都会有指针移动。而朴素的算法的问题就在于指针经常回溯到之前的位置，双指针算法的模板一般都可以写成下面的形式(模板)：

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

因为双指针算法是一种优化时间复杂度的方法，所以我们可以首先写出最朴素的两层循环的写法。
然后考虑题目中是否具有单调性。即当其中一个指针向后移动时，在希望得到答案的情况下，另一个指针是不是只能向着一个方向移动。
如果是，说明题目具有单调性，可以通过双指针算法优化。

Reference Documents

[1] 双指针算法
[2] 双指针算法详解