AcWing 799. 最长连续不重复子序列

题目链接：点击这里

技巧：怎么判断区间 $[j,i]$[j,i] 里没有重复数字呢？

开一个数组 $s[\ ]$s[ ] 记录每一个元素出现的次数，每一个 $a[i]$a[i] 进来 $s[a[i]]$s[a[i]] 就加 $1$1，$a[j]$a[j] 出去 $s[a[j]]$s[a[j]] 就减 $1$1，那么，若 $s[a[i]] > 1$s[a[i]]>1，则表明有重复元素。

时间复杂度为 $O(n)$O(n)：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    
    int ans = 0;
    for(int i = 0, j = 0; i < n; ++i)
    {
        s[a[i]]++;
        while(s[a[i]] > 1)
        {
            s[a[j]]--;
            j++;
        }
        ans = max(ans, i - j + 1);
    }
    
    printf("%d\n", ans);
    
    return 0;
}