双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形

双指针经典例题分析总结

双指针算法模型定义

概述

双指针算法概念比较广泛, 只要使用了两个有关联的循环变量, 也许都能叫做双指针算法

分类

根据循环方向的不同, 可以分类为:

• 同向双指针: 循环变量方向相同
• 相向双指针: 循环变量方向不同

根据遍历对象的不同, 可以分类为:

• 同一对象双指针: 两个循环变量在同一对象上遍历
• 不同对象双指针: 两个循环变量在不同对象上遍历

上述分类方法有点太抽象, 根据实际问题可以这样分类:

• 快慢指针

常用于链表中

• 滑动窗口

常用于数组中

• 同一序列中的相向双指针

如快排

定义

由于双指针算法应用太广泛, 这里狭义地定义一下双指针算法, 以缩小研究对象, 更好地研究问题的解决办法

由于本人水平有限, 这里我并不清楚这种定义方法是否“狭义”, 即是否适用于所有双指针算法

双指针算法:

两个关联的循环变量 $i$ 和 $j$, 下标对 $(i,j)$ 指代某个对象,

其中, $j = f(i)$ 具有单调性, 即随着 $i$ 的递增, $j$ 递增或递减

问题的结果跟对象的属性或由对象属性延伸出的某个信息有关

注意, 一般认为 $(i,j)$ 可以表示二重循环中的任一情况,

这里定义的 $(i,j)$ 是上述的子集, 可以认为对于每个 $i$, 都有唯一一个 $j = f(i)$ 与之对应

举例

问题:

给定长度为 n 的序列, 找出最长不含重复元素区间的长度

$(i,j)$含义:

$(i,j)$ 指代某个区间

对于每个 $i$, $i$ 为区间右端点,

$j$ 表示所有不含重复元素区间 $[j,i]$ 中离 $i$ 最远的左端点

样例:

1 2 2 3 5

下标从 1 开始

$i = 1$ 时, $j = 1$, 区间为 $[1,1]$

$i = 2$ 时, $j = 1$, 区间为 $[1,2]$

$i = 3$ 时, $j = 3$, 区间为 $[3,3]$

$i = 4$ 时, $j = 3$, 区间为 $[3,4]$

$i = 5$ 时, $j = 3$, 区间为 $[3,5]$

答案为所有满足条件 $(i,j)$ 中最长区间的长度, 即区间 $[3,5]$ 的长度 3

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} < j$

根据定义可知 $[j^{\prime},i+1]$ 是不含重复元素的区间

$\therefore$ $[j^{\prime},i]$ 也是不含重复元素的区间

根据 $j = f(i)$ 的定义, 显然 $j^{\prime} \geq j$, 产生矛盾

$\therefore$ $j^{\prime} \geq j$, $j = f(i)$ 单调递增, 符合单调性

准确来说 $j = f(i)$ 单调不减, 即非严格单调递增

循环方向:

由于 $j = f(i)$ 单调递增, 所以 $j$ 的遍历方向为 $1\rightarrow m$

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], cnt[N];

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) cin >> a[i];

    int res = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        cnt[a[i]]++;

        while(j <= i && cnt[a[i]] > 1) cnt[a[j++]]--;

        res = max(res, i - j + 1);  // 跳出 while 循环后的 j 就是定义中对应 i 的那个 j, 可以用来筛选最终结果
    }

    cout << res << endl;

    return 0;
}