Introduction

双指针是一种根据单调性优化朴素暴力遍历方法的算法

这里提到的单调性一般是不严格的，即某个指针只可能向后移动或者不动，而不可能向前移动

朴素算法

for (int i = 0; i < n; i ++ ) 
    for (int j = 0; j < n; j ++ )
        // 需要执行的语句

朴素算法中，需要两层完整的循环，i循环语句执行n次，j循环语句执行n²次，则时间复杂度为$O(n^2)$

双指针优化

for (int i = 0; i < n; i ++ ) 
    while (j < i && check(i,j)) j ++;
        // 需要执行的语句

使用双指针优化之后，i循环语句仍然执行n次，但内部的while循环语句最多执行n次，则一共最多执行2n次，时间复杂度为$O(n)$

对比

经过优化之后，相当于每次i更新时，j指针不必回溯到开始位置。

Example

Question：给定一个字符串，由小写字母和空格组成，空格不会连续出现两个或以上，字符串首位不是空格。输出字符串内所有单词（由空格隔开的每个纯字母字符串算作一个单词）

思路

先看一下普适板子：

for (int i = 0; i < n; i ++ ) 
    while (j < i && check(i,j)) j ++;
        // 需要执行的语句

我们让i指针负责从头走到尾，然后j每次从i开始，向后扫描，直到扫描完一个单词，即扫描到空格为止

之后更新i 的位置：j的下一个位置是下一个单词的首字母

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int main () {
    char str[1000];
    fgets(str, 1000, stdin);
    // 被迫使用fgets，gets不能用了

    int n = strlen(str);
  
    for (int i = 0; i < n; i ++ ) 
    {
        int j = i;
        // i指向单词首字母，让j从这里开始扫描
        while (j < n && str[j] != ' ') j ++;
        // 一旦j扫描到全串结尾
        // 或者
        // j扫描到空格
        // 就，停止扫描，j指向空格
  
        for (int k = i; k < j; k ++ ) printf("%c", str[k]);
        //输出整个单词
  
        puts("");
        // 换行

        i = j;
        // 更新i的位置，让i指向j的位置，也就是空格
        // for循环结束时会让i++，即指向下一个单词首字母
    }
    return 0;
}

好了，你已经掌握了双指针算法的基本原理，快做一道题看看吧

Question

$$ \begin{align} &给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。\hspace{2cm}\\ &\textbf{输入格式}\\ &第一行包含整数 n。\\ &第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。\\ &\textbf{输出格式}\\ &共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。\\ &\textbf{数据范围}\\ &1\le n \le 10^5\\ \end{align} $$

输入样例：

5
1 2 2 3 5

输出样例：

3

思路

朴素做法

非常暴力，直接遍历

for (int i = 0; i < n; i ++ ) 
    for (int j = 0; j <= i; j ++ )
        if (check(i,j)) 
            res = max(res, i - j + 1);

相当于没有任何的巧妙之处，两次遍历可以直接构造出所有的子串。每次判断其中是否有重复的元素即可，再与当前的答案比较

双指针优化

设置两个指针i和j，其中包含的是没有重复的数的连续区间。不妨让i指针在右，j指针在左

让i指针为主动指针，j为从动指针。由此，我们可以确定单调性：

j只能向右移动或者不动，不能向左移动

因为i每次向右移动一位，就是给子串中添加了一个元素，这就导致字串内可能出现重复元素。如果重复，就让j向右移动一位，以去除重复

如此一来，我们可以确保两指针之间为无重复元素的子串，并且i和j总移动次数不会超过2n次

for (int i = 0; i < n; i ++ ) 
{
    while (j <= i && check(i,j)) j ++;
    res = max(res, i - j + 1);
}

至此，我们已经完成了双指针的优化算法，接下来处理 判定子串内是否存在重复

判断子串是否存在重复

我们使用一种用空间换时间 的算法：开设一个数组，存下每个数字出现的次数，初始化为0。每次新加元素到子串时，判断该数组对应元素是否大于1即可

int s[N];

对该数组只有两个操作：

1. i指针后移时，对应元素加1
2. j指针后移时，对应元素减1

for (int i = 0, j = 0; i < n; i ++ ) {
    s[a[i]] ++;
    // i后移，进入新元素，s数组加一
    while (s[a[i]] > 1 ) {
        s[a[j]] --;
        // j后移，元素出列，s数组减一
        j ++;
    }
    res = max(res, i - j + 1 );
}

至此，已经完成了核心部分的代码

这里有一个比较细致的点：为什么while循环不需要判断j <= i呢？

因为当j > i时，子串中已经没有元素了，相当于s数组的所有元素都为0，此时s[a[i]] > 1就一定不成立了。换言之，如果s[a[i]] > 1成立，那么j <= i也一定成立，不需要重复判断

#include <iostream>
#include <cstdio>
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[i]);
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ ) {
        s[a[i]] ++;
        while (s[a[i]] > 1 ) {
            s[a[j]] --;
            j ++;
        }
        res = max(res, i - j + 1 );
    }
    cout << res << endl;
    return 0;
}