题目描述

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

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

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

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

数据范围
1≤n≤100000

样例

输入样例：
5
1 2 2 3 5
输出样例：
3

题解

(双指针算法) $O(n)$

~刚入门小萌新，第一次尝试写题解，有诸多错误和不足，希望大家指正~

该题目可以通过双指针算法优化暴力做法，把复杂度O(n^2)减少到O(n)。
这里的双指针属于“对于一个序列，用两个指针维护一段区间”， “i指针”在右，“j指针”在左；
在用 i 遍历数组时的每一次循环中，都使 j 在离 i 最远的且满足“连续不重复子序列”的位置，用 ans 记录最大的区间长度(i - j + 1);
最主要的问题就是怎么写模板中的check(),这里用另外一个数组 s[ ] 来记录[ j, i ]区间中每个数字出现的次数。

1、“i指针”每往后移动一次，[ j , i ]区间就要增加一个数，对应的数字a[i]的个数就要 +1；
2、当s[ a[i] ] > 1时， 说明[ j, i ]区间内出现了重复数字，显然这个重复数字是与当前a[ i ]重复的，但是不知道这个数字具体在哪个位置。所以用“j指针”来找这个重复数字———“j指针”往后移动，把经过的数字从[ j , i ]中去除，并让对应的该数字的个数 -1，直到s[ a[i] ] = 1时，区间[ j , i ]又满足要求；
3、更新ans的值，继续遍历数组直到结束。

注：在循环中“ j 指针”是不可能超过“ i 指针”的，所以在while() 中不必判断j <= i;

~ 感谢您看能够完^_^ ~

时间复杂度

由于 i 和 j 都只会向前走，直到数组结束，所以看似是两重循环，但是走过的步数也只有 n + n = 2n 步，所以时间复杂度为$O(n)$

参考文献

y总算法基础课第一章第三节

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, ans = 0;
int a[N], s[N];  //a[]为原数组，s[]数组用来记录[j,i]这个区间内各个数字的出现次数

int main()
{
    cin >> n;

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

    for(int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++; //“i指针”每往后移动一次，[j,i]区间就要增加一个数，对应的a[i]个数就要 +1
        while(s[a[i]] > 1) 
        {
            s[a[j]]--; //“j指针”往后移动，把重复的数从[i,j]中去除
            j++;
        }

        ans = max(ans, i - j + 1); //每次取区间最大值
    }

    cout << ans << endl;

    return 0;
}