题目描述

不用写了吧。。。

算法

桶，map的常数有点大，这里的数据范围只是10000，显然有点大材小用。
这里c数组当作桶。存储最后一个a出现的位置i
front代表窗口里的第一个数的位置，不难发现，答案即为i-front+1的最大值
每次输入a，查看是否a曾在桶中出现，
一旦曾经出现，即：c[a]>0，
就判断是否已经被排出，c[a]>=front
没有排出就尝试更新front指针
否则不管
tot每次记录最优答案。
注意a[c]还要更新。

时间复杂度

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
const int Maxn=100205;
int front =1 ;
int c[Maxn];
int tot=0;
int main()
{
    scanf("%d",&n);
    int a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);

        if(c[a]>0)
            if(c[a]>=front)front=c[a]+1;

        if(i-front+1>tot)tot=i-front+1;
        c[a]=i;
    }
    printf("%d",tot);
    return 0;
}