799. 最长连续不重复子序列
摘要
Title: 799. 最长连续不重复子序列
Tag: 双指针
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
799. 最长连续不重复子序列
-
题意
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
-
思路
模板
1
2
3
4
5
6j = 0
for i in range(n):
while j < i and check(j, i):
j += 1
...
...运用场景：
- 对于一个序列，用两个指针维护一段区间
- 维护两个指针，左指针j，右指针i，保证两个指针都是单调的
i: 指定区间的右边界
j: 指定区间的左边界
它的含义为: 当i固定时j往左最远能到什么地方
- 维护两个指针，左指针j，右指针i，保证两个指针都是单调的
- 对于两个序列，维护某种次序，比如归并排序种合并两个有序序列的操作
此题的逻辑为第一种运用场景，当i往右移时，新进区间的值，如果被标记了，就说明区间里有这个值，那么就把j往右移即可，直到那个值被弹出去
- 对于一个序列，用两个指针维护一段区间
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24'''
Author: NEFU AB-IN
Date: 2022-01-25 17:28:23
FilePath: \ACM\Acwing\799.py
LastEditTime: 2022-01-25 17:39:28
'''
from collections import Counter
d = Counter()
if __name__ == "__main__":
n = int(input())
lst = list(map(int, input().split()))
j = 0
res = 0
for i in range(n):
d[lst[i]] += 1
while j < i and d[lst[i]] == 2:
d[lst[j]] -= 1
j += 1
res = max(res, i - j + 1)
print(res)