15836 小埋的优雅序列 题解

经验分享区
1

题目描述

小埋最近迷上了优雅序列。
优雅序列的定义是，在一段连续的序列中，包含的数字中不会出现重复数字。
现在给你一个长度为n的数组，请你告诉小埋其中最长的优雅序列的长度是多少。

输入格式

第一行是一个正整数 n , n 表示数组的长度。

第二行有 n 用空格隔开的正整数，有 n 个整数数字 i 。

输出格式

一个整数，符合题目要求的最长子数组的长度。

样例 #1

样例输入 #1

5
1 2 3 1 2

样例输出 #1

3

样例 #2

样例输入 #2

9
1 1 1 2 2 2 1 1 3

样例输出 #2

2

提示

1<=n<=2∗10^5

1<=i<=2∗10^5

做过

非常明显的双指针+map

首先，检测一个数是否被使用过，明显使用map。
而序列考虑使用双指针。

思路

我们考虑将遍历的数作为它的序列的结尾，调整序列的开头来使这个序列成为“优雅序列”。

每次遍历的数都加入map，当遍历到map记录过的数时，调整开头，直到这个序列只包含一个这次遍历的数。

下面为部分代码：

int l=1,r=2;//l为开头，r为结尾
mp[a[1]]=1;
while(r<=n){
    if(mp[a[r]]){//如果记过
        while(a[l]!=a[r]) mp[a[l]]=0,l++;//调整开头
        l++;
    }
    mp[a[r]]=1;//记入map
    res=max(res,r-l+1);
    r++;//一定要放到后面，否则喜提90pts
}
1 个赞