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

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

Powered by:NEFU AB-IN

link

文章目录

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

题意思路代码

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

题意

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

思路

模板

j = 0
for i in range(n):
  while j < i and check(j, i):
    j += 1
    ...
  ...

维护两个指针，左指针j，右指针i，保证两个指针都是单调的
i: 指定区间的右边界
j: 指定区间的左边界
它的含义为: 当i固定时j往左最远能到什么地方

此题的逻辑为，当i往右移时，新进区间的值，如果被标记了，就说明区间里有这个值，那么就把j往右移即可，直到那个值被d出去

代码

'''
Author: NEFU AB-IN
Date: 2022-01-25 17:28:23
FilePath: ACMAcwing799.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)