双指针&双向搜索

双指针

基本介绍

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

双指针是一个相当宽泛的思想，在许多算法中也有应用。快速排序算法便是通过两个相向移动的指针，实现了按元素与基准元素的比较结果划分数组，从而得以分别向两边递归，常数远小于朴素算法。

【模板】数对计数问题

题目描述

给定长度为 $n$ 的严格增序列 $\{a_n\}$ 和整数 $m$，求序列中有多少对不同的数相加和超过 $m$。

数据范围

对于 $100\%$ 的数据，$1\le n\le10^6$，$|a_i|,|m|\le10^9$

朴素算法

直接用两重循环枚举 $i,j\,(1\le im$。

时间复杂度 $O(n^2)$。

二分算法

在朴素算法中，我们舍弃了给定序列严格增的性质。

$a_i+a_j>m\iff a_j>m-a_i$，用一重循环枚举 $i\,(1\le i\le n)$，然后根据给定序列严格增的性质，只需在给定序列上二分查找找到满足 $a_j>m-a_i$ 的最小下标 $j$（或 $j$ 不存在）便可以省去朴素算法中枚举 $j$ 的第二重循环，并在 $1\le i

时间复杂度 $O(n\log n)$。

双指针算法

既然给定序列是严格增的，还是先用一重循环从小到大枚举 $i\,(1\le im-a_i$ 最小的下标 $j$（或 $j$ 不存在，此时令 $j=n+1$）显然是随着 $i$ 的增大而单调不增的，因此每次都二分查找显得很冗余。只需额外维护这个最小的 $j$，令其初始值为 $n+1$，在枚举 $i$ 的同时实时判断维护的 $j$ 能否更新为更小的下标即可。

分析时间复杂度，$i$ 从小到大变化 $n$ 次，$j$ 从大到小最多也变化 $n$ 次。故时间复杂度为 $O(n)$。

代码实现

双指针代码：

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$ 的完全下届，除了 $a_j>m-a_i$，最原始的条件 $1\le i

虽然代码中的 i 和 j 并不是严格意义上的指针，但具备类似指针的定位功能，我们仍把它们叫做双指针。

优缺点

通过上一题，我们发现双指针强大主要在于利用单调性（相关性）去掉一重循环，达到线性复杂度。

缺点也很明显，双指针之间的关系特别依赖题目本身的性质。

尺取法

前面一题用到了相向移动的双指针，但是在一般的题目中，同向移动的双指针实则更加常见。

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

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

1 2	for (int i = 1, j = 1; i <= n; ++i) while (a[i] != a[j]) ++j;

Floyd 判环算法

假设链表内的各元素均有一个后继，结构成 $\texttt{P}$