双指针算法
作者:
成理第一深情
,
2024-01-04 14:30:10
,
所有人可见
,
阅读 66
Acwing 799.最长连续不重复子序列
题解
i
和j
都从下标0
开始,j
往后走的过程中count[a[j]]+=1
,当出现count[a[j]]>1
的情况时,说明有重复的数了,那么就开始动i
指针,需要把i
指针移到重复的位置的下一个位置。i
指针移动的过程中要把count[a[i]]-=1
。
- 时间复杂度分析:
j
从0
走到n-1
。对于每一个j
,i
平均最多只会动一次。所以是O(n)
a = [0] * 100010
count = [0] * 100010
def main():
n = int(input())
a = list(map(int, input().split(' ')))
i = 0
res = 0
for j in range(0, n): # j每次要往右边走
count[a[j]] += 1 # 记录走的过程中的数的数量
while count[a[j]] > 1: # 只要发现了有重复的数,那么就去找重复的位置,一个位置是当前的j,另一个位置就要用i来找
count[a[i]] -= 1
i += 1
res = max(res, j - i + 1) # 即使没有重复数字,j每走一步也会更新一下最长,而不是等到重复了才更新
print(res)
main()