【题解】普及三秋季-线性技巧综合训练例题-上午 练习T3

小埋的优雅序列(据说也叫百万富翁的第二次实验QaQ)

题目描述

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

输入格式

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

第二行有nn用空格隔开的正整数,有 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;


暴力打法(50pts)

我们可以发现,这道题的暴力打法就是枚举 i ,当 i=1 时,优雅序列的中止在哪里,随后一直到 i=n

在枚举时,我们需要使用 map ,每到一个点就判断 map ,从而找到最长的序列。

核心代码:

    int sum=1,ans=0;
	for(int i=1;i<=n;i++){
		mp[a[i]]=1;
		for(int j=i+1;j<=n;j++){
			if(mp[a[j]]==1) break;
			mp[a[j]]=1;
			sum++;
		}
		ans=max(ans,sum);
		sum=1;
		memset(mp,0,sizeof mp);
	}

正解(100pts)

考虑双指针:将遍历的数->它的序列的结尾 随后调整序列的开头来使这个序列成为“优雅序列”。

每次遍历的数都要放入 map ,当遍历到 map 有的数时,调整开头,直到这个序列只包含一个这次遍历的数。

核心代码:

	int l=1,r=2,ans=0;
	mp[a[1]]=1;
	while(r<=n){
	    if(mp[a[r]]==1){
	        for(;a[l]!=a[r];l++){  
			    mp[a[l]]=0;  
			}
	        l++;
	    }
	    mp[a[r]]=1;
	    ans=max(ans,r-l+1);
        r++;
	}

(蒟蒻菜的要死,这题写了1小时)

2 个赞

谢谢思路,我想了半个小时。

1 个赞

我也想过差不多的思路,但是没想到用map

别谢我,我前两题全不会

第二题可以给你一点思路:
用双指针 l,r ,再求出两个指针遍历到的最大值 lmax,rmaxlmax<rmaxl 向右移动,反之 r 向左移动。

可以自己画个图推一下,我这个方法是借鉴博客的。

或者自己上百度搜一下。

我在写T1
(hh,A了)

恭喜!