题目描述

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

输入格式:
第一行包含整数 n。
第二行包含 n个整数（均在0∼105范围内），表示整数序列。

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

样例

输入样例：

5
1 2 2 3 5

输出样例：

3

算法:用队列维护窗口

时间复杂度

O(n)

C++ 代码

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;

const int N=100001;
int n,arr[N];
int main()
{
    cin>>n;
    //O(n)
    for(int i=0;i<n;i++) cin>>arr[i];

    queue<int> q;
    unordered_map<int,int> up;
    int Maxsize=0;

    for(int i=0;i<n;i++)
    {
        up[arr[i]]++;
        q.push(arr[i]);
        //只有一个当前元素
        if(up[arr[i]]==1)
        {
            if(Maxsize<q.size()) Maxsize=q.size();
        }
        //两个当前元素
        else
        {
            while(up[arr[i]]==2)
            {
                int front=q.front();
                q.pop();
                up[front]--;
            }
        }
    }
    cout<<Maxsize<<endl;
    return 0; 
}