双指针算法

franciscochonge

双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。
它包含两种形式：

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

一般更多使用、也更难想到的是第2种情况。
<hr/>双指针算法最核心的用途就是优化时间复杂度。
【核心思想】：

原本两个指针是有 种组合，因此时间复杂度是  。
而双指针算法就是运用单调性使得指针只能单向移动，因此总的时间复杂度只有 ，也就是。

之所以双指针可以实现  的时间复杂度是因为指针只能单向移动，没有指针的回溯，而且每一步都会有指针移动。
而朴素的  算法的问题就在于指针经常回溯到之前的位置。
<hr/>双指针算法的模板一般都可以写成下面的形式(模板)：
for (int i = 0, j = 0; i < n; i++)
{
    while (j < i && check(i, j)) j++;

    // 每道题目的具体逻辑
}
因为双指针算法是一种优化时间复杂度的方法，所以我们可以首先写出最朴素的两层循环的写法。
然后考虑题目中是否具有单调性。
即当其中一个指针  向后移动时，在希望得到答案的情况下，另一个指针  是不是只能向着一个方向移动。
如果是，说明题目具有单调性，可以通过双指针算法优化。
<hr/>下面举一个例子详细说明双指针算法。
例题：ACWing 799. 最长连续不重复子序列

题目描述：
给定一个长度为  的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式:
第一行包含整数 。
第二行包含  个整数，表示整数序列。
输出格式:
共  行，每行 个整数，表示所有操作进行完毕后的最终矩阵
输入样例
5
1 2 2 3 5
输出格式:
3

注意这里我们要找的是最长的、连续的、不重复的、子序列，所以上面例子中 2 3 5 是最终的答案。



题目示例

如果是两层for循环处理，每次处理以i为起点，以j为终点的连续子序列是否是连续不重复的子序列，那两层循环的时间复杂度就是 。
而判断一个连续子序列是否是连续不重复子序列又需要遍历[i, j] 这个子序列来判断，这一步需要的时间。
所以总的时间复杂度就是 了。
这里面我们容易发现我们判断 [i, j] 子序列是否是连续不重复子序列时， 这里与判断 [i, j - 1] 这个子序列是否是连续不重复子序列相比存在大量的重复计算。
而且，如果[i, j] 是连续不重复子序列，那 [i, j - 1] 肯定也是连续不重复子序列。
但是，答案肯定不是 [i, j - 1]，因为 [i, j] 的长度比 [i, j - 1]长，题目要求找的是最长的连续不重复子序列。
所以我们简单变一下思路：
假设每次我们的目标是选择以 i 为起点的子序列中，最长的连续不重复子序列对应的下标位置。这样就能得到一个朴素的  的解法，这个思路是很简单的。
下面是代码实现：
#include<iostream>

using namespace std;

const int N = 100010;
int a[N], s[N];

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a);

    int res = -1;
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        int j = i;
        while (j < n)
        {
            if (s[a[j]] >= 1) break;
            s[a[j++]]++;
        }
        res = max(res, j - i);

        // 将计数复原
        for (int k = i; k < j && k < n; k++) s[a[k]]--;
    }

    printf("%d\n", res);
    return 0;
}
上面的代码中定义 s 表示值为 i 的元素出现的次数。 用这个数组相当于用 map 记下来每个元素出现的次数，从而能比较方便的判断出当前序列中是否有重复元素。
另外，需要清楚的知道 i, j 在每次循环跳出的时候指向了什么位置。
我们这里看判断条件 if (s[a[j]] >= 1) break; 可以知道当 a[j] 这个数之前已经出现过的时候，才会跳出。
因此，j这个元素应该已经不能满足序列不重复了，因此从i到j-1表示的是满足题意的序列。
所以，最终的长度是 j - i，而不是 j - i + 1。
<hr/>现在我们已经得到了  时间复杂度的算法，然后我们看一下是否具有单调性。
如果有，则可以使用双指针将其优化到 。
现在我们假设终点为 ，以  为终点，向左找到最长的连续不重复子序列，起点定义为 。
也就是说， 是以  为终点的最长连续不重复子序列。
这里与前面的定义有点不太一样，需要注意一下。
如下图所示。



双指针算法i, j定义的图示

下面考虑单调性：
当  向后移动时， 是否可以沿着一个方向移动？
我们经过考虑，答案是当  向后移动时， 不可能向前移动，这就表示这个方案具有单调性。



当 i 向后移动时，j 不可能向前移动

我们可以使用反证法证明：

  假设  是以  为终点的最长连续不重复子序列。如果当  向后移动时(比如到 )，却向前移动了(比如到 )。
说明了  是以  为终点的最长连续不重复子序列，这就表示 范围内都没有重复元素。
即：以  为终点的最长连续不重复子序列应该是 而不是
（因为 中肯定没有重复元素，而且区间长度还比 长。）
这就与题设的 是以  为终点的最长连续不重复子序列相矛盾。
因此可证明：
当  向后移动时， 不可能向前移动 （可能不动，也可以向后，就是不可能向前）。

当我们证明单调性之后，可以写出使用双指针模板的代码:
#include<iostream>

using namespace std;

const int N = 100010;
int a[N], s[N];

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a);
   
    int res = -1;
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a]++;
        while (j < i && s[a] > 1) s[a[j++]]--;
        
        res = max(res, i - j + 1);
    }

    printf("%d\n", res);
    return 0;
}
代码中循环内的部分有点绕。
【主要思想】：

  如果可能重复，一定是刚加进来的这个元素重复了，因为在他加进来之前是连续不重复子序列的状态。
所以当进入for循环之后，先把当前元素的个数加上1，然后如果包含了重复元素就后移j指针，直到s[a] == 1为止。

<hr/>以上就是有关双指针算法的所有内容。
想要学习更多有关算法的知识，可以关注我的个人公众号：程序员阿sir