双指针

基本介绍

双指针（Two-pointer），即同时维护两个指向数组下标或者链表位置的指针，并实时控制它们同向或相向移动，以达到大幅提升枚举的效率、寻找满足条件的极长段等目的。

双指针是一个相当宽泛的思想，在许多算法中也有应用。快速排序算法便是通过两个相向移动的指针，实现了按元素与基准元素的比较结果划分数组，从而得以分别向两边递归，常数远小于朴素算法。 ### 【模板】数对计数问题 #### 题目描述 给定长度为 n 的严格增序列 {an} 和整数 m，求序列中有多少对不同的数相加和超过 m。 #### 数据范围 对于 100% 的数据，1 ≤ n ≤ 106，|ai|, |m| ≤ 109 #### 朴素算法 直接用两重循环枚举 i, j (1 ≤ i < j ≤ n)，统计有多少对 ai + aj > m。

时间复杂度 O(n2)。 #### 二分算法 在朴素算法中，我们舍弃了给定序列严格增的性质。

ai + aj > m ⇔ aj > m − ai，用一重循环枚举 i (1 ≤ i ≤ n)，然后根据给定序列严格增的性质，只需在给定序列上二分查找找到满足 aj > m − ai 的最小下标 j（或 j 不存在）便可以省去朴素算法中枚举 j 的第二重循环，并在 1 ≤ i < j ≤ n 的吸纳之下直接算出合法 j 的个数。

时间复杂度 O(nlog n)。 #### 双指针算法 既然给定序列是严格增的，还是先用一重循环从小到大枚举 i (1 ≤ i < n)。注意到满足 aj > m − ai 最小的下标 j（或 j 不存在，此时令 j = n + 1）显然是随着 i 的增大而单调不增的，因此每次都二分查找显得很冗余。只需额外维护这个最小的 j，令其初始值为 n + 1，在枚举 i 的同时实时判断维护的 j 能否更新为更小的下标即可。

分析时间复杂度，i 从小到大变化 n 次，j 从大到小最多也变化 n 次。故时间复杂度为 O(n)。 #### 代码实现 双指针代码： 

1
2
3
4
for (int i = 1, j = n + 1; i <= n; ++i) {
  while (j > 1 && a[j - 1] > m - a[i]) --j;
  ans += n + 1 - std::max(j, i + 1);
}
这里的 std::max(j, i + 1) 返回的是 j 和 i + 1 中的较大值，因为维护的 j 还不是合法 j 的完全下届，除了 aj > m − ai，最原始的条件 1 ≤ i < j ≤ n 任需满足。

虽然代码中的 i 和 j 并不是严格意义上的指针，但具备类似指针的定位功能，我们仍把它们叫做双指针。 ### 优缺点 通过上一题，我们发现双指针强大主要在于利用单调性（相关性）去掉一重循环，达到线性复杂度。

缺点也很明显，双指针之间的关系特别依赖题目本身的性质。 ### 尺取法 前面一题用到了相向移动的双指针，但是在一般的题目中，同向移动的双指针实则更加常见。

双指针的变量 i, j，当从小到大枚举 i 的同时，j 也随之从小到大变化，视觉效果上像是一把向右移动的尺子测量者数轴上 i, j 间的一段，“尺取法”由此得名。

给定长度为 n 的序列 {an}，以下代码能在每次 while 循环结束后，得到当前枚举的 i 下 aj, aj + 1, …, ai 只包含一种值的最小 j： 

1
2
for (int i = 1, j = 1; i <= n; ++i)
  while (a[i] != a[j]) ++j;
### Floyd 判环算法 假设链表内的各元素均有一个后继，结构成 P