最长连续不重复子序列

题目

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

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

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

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

数据范围 $1≤n≤10^5$

输入样例：

5
1 2 2 3 5

输出样例：

3

思路

步骤如下：

1. 遍历存放的整个数组，$l、r$为左右指针
2. a[i] 出现次数 b[a[i]] + 1
3. 存在重复值时左指针 $l$ 右移且对应的值次数减 $1$
4. 更新最大值 res = max(res, r - l + 1)

代码

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], b[N];  // a存储数值，b存储第i个数出现的次数

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    int res = 0;
    for (int l = 0, r = 0; r < n; r ++ )
    {
        b[a[r]] ++ ;  // 对应值出现次数加1
        while (b[a[r]] > 1)  // 存在重复值则循环
        {
            b[a[l ++ ]] -- ;  // l右移且对应的值出现次数减1
        }
        res = max(res, r - l + 1);  // 更新最大长度
    }
    
    printf("%d", res);
    
    return 0;
}

【转自：东台网页开发公司 http://www.1234xp.com/dongtai.html 提供，感恩】