【AcWing算法基础】第一讲-基础算法-双指针算法 AcWing 799. 最长连续不重复子序列

摘要：
一道经典的双指针题目。

题目

给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式
第一行包含整数 $n$。

第二行包含 $n$ 个整数（均在 $[0, 100000]$ 范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围
$1≤n≤100000$

输入样例：

5
1 2 2 3 5

输出样例：

3

双指针

双指针的核心思想，是在暴力求解的基础上，通过已知的某种性质，用两个指针进行优化。
维护两个指针 $i$，$j$，维护一个计数数组，$i$ 负责遍历原数组，在此过程中用计数数组计数。当i到某一个位置对应的计数数组数值超过 $1$，则认为从 $j$ 到 $i$ 这一段出现了重复。当前最长不重复段为 $i - j + 1$. 接下来移动 $j$，并通过计数数组最后一个值监控 $j$ 扫过的让最后一个值超过 $1$ 的下标，当 $j$ 到达这个下标时，我们认为找到了和 $i$ 处重复的值，那么，$j + 1$ 的位置到 $i$ 这一段不可能出现重复，$j$ 在此固定不动，$i$ 继续向后遍历，直到遍历完所有数字。

#include <iostream>
#define IOS ios::sync_with_stdio(false)
using namespace std;

int n;
const int N = 100010;
int a[N], S[N];                                     // 3

int main()
{
    IOS;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ ) {
        S[a[i]] ++;                                 // 1
        for (;S[a[i]] > 1;) {                       // 2
            S[a[j]] --;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    cout << res;
    return 0;
}

每一次 i 移动，让对应数字对应的计数数组下标 $+1$;

保持计数数组非零值全为 1，一旦i移动后造成对应计数数组值> 1，就认为出现了重复
此时移动 j，直到找到 i 对应的数的重复数字，并且将移动前 j 对应的数字在计数数组中抹去 $1$ 个。如果抹去 $1$ 位当前 j 对应的数字恰好造成了 i 对应的数字总数不大于 $1$ 了（本来是大于 $1$暂停的），那么此时就认为是通过 j 找到了重复值。此时 j 继续加一位，那么现在从 j 到 i 都是不重复的。

计数数组之所以和原数组开一样大的空间，是因为根据题意，原数组每个数大小不超过 $100000$。

计数数组维护序列的不重复性。 这道题还有个亮点就是计数数组的使用。为了监控不重复序列，维护一个数值始终为 $0$ 或 $1$ 的计数数组，每一次 i 移动，更新计数数组的对应值，一旦该值超过了 $1$，我们就知道出现了重复。妙啊，妙。

复杂度分析：
因为 i 和 j 双指针最多可以执行 $2n$ 次，所以时间复杂度最高为 $O(n)$.

原题链接： AcWing 799. 最长连续不重复子序列