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

2021-06-03 23:06

阅读：6793

标签：整数答案 pac 出现联系起点 lap int 说明

网址 https://www.acwing.com/solution/AcWing/content/2069/

题目描述
给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。

算法1
(枚举) O(n)O(n)
滑动窗口记录窗口的起始点 l r
同时使用一个数组或者map记录该窗口区间各个数字出现的次数(后来证明使用map会超时)
vector[HTML_REMOVED] v(N,0);

如果r增加的时候添加的元素在区间已经有了那么就从窗口起点开始逐个弹出直到将重复的元素弹出
这样r就可以添加滑动窗口区间了

if (m[v[r]] ) {
//说明r中的元素已经在滑动窗口区间出现了那么需要将区间里的元素弹出
while (v[l] != v[r]) {
if(m[v[l]]) m[v[l]]--;
l++;
}
if (m[v[l]] )m[v[l]]--;
l++;
}
每次添加成功记录窗口的长度值和答案比较答案取值其中最大的值
ans = max(ans, r - l + 1);

 1 #include  2 #include set>
 3 #include  4 #include  5 using namespace std;
 6 
 7 const int N = 1000010;
 8 
 9 vectorint> v(N,0);
10 
11 int t;
12 int n;
13 
14 int ans  = -1;
15 
16 vectorint> m(N,0);
17 
18 int main()
19 {
20     cin >> t;
21     for(int i = 1;i){
22         cin >> v[i];       
23     }
24 
25 
26     int l = 1; int r = l+1;
27     m[v[l]]++;
28     while (l  t) {
29         if (m[v[r]] ) {
30             //说明r中的元素 已经在滑动窗口区间出现了 那么需要将区间里的元素弹出
31             while (v[l] != v[r]) {
32                 if(m[v[l]]) m[v[l]]--;
33                 l++;
34             }
35             if (m[v[l]] ) m[v[l]]--;
36             l++;
37         }
38         //r索引元素进入滑动窗口
39         m[v[r]]++;
40         ans = max(ans, r - l + 1);
41 
42         //下一轮比对
43         r++;
44     }
45 
46     cout  endl;
47 
48     return 0;
49 }
50 
51 作者：defddr
52 链接：https://www.acwing.com/solution/AcWing/content/2069/
53 来源：AcWing
54 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

View Code

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

标签：整数答案 pac 出现联系起点 lap int 说明

原文地址：https://www.cnblogs.com/itdef/p/10886600.html

上一篇：在做爬虫或者自动化测试时新打开一个新标签页，必须使用windows切换

下一篇：AcWing 803. 区间合并

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 799. 最长连续不重复子序列
文章链接：http://soscw.com/index.php/essay/90162.html

亲，登录后才可以留言！

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

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing&#160;799.&#160;最长连续不重复子序列

评论

热门文章

推荐文章

最新文章

置顶文章

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