双指针,第一个指针是i,第二个指针是check函数中的index。
核心过程是维护一个数组,该数组不包含两个同样的整数。
为什么能降低时间复杂度:
1、任意时刻i的最长队列长度是建立在i-1时刻的长度基础之上的,因此不需要在全范围搜索第二个指针。
2、无重复整数的数组长度不可能太大,因此每一次在新数组上检索重复整数的时间是常数。
N = int(input())
sequence = list(map(int, input().split()))
def check(my_list, new_num):
global max_len, index
if new_num in my_list:
index = my_list.index(new_num)
my_list = my_list[index + 1:]
my_list.append(new_num)
max_len = max(max_len, len(my_list))
return my_list
max_len = 0
index = 0
my_list = []
for i in range(N):
my_list = check(my_list, sequence[i])
print(max_len)
这个做法超时了