查找具有所有数字的最小长度子数组

Question

文件input.txt由两行组成：首先具有整数N个空格，然后具有整数K（1 ?? N，K ?? 250000）。第二个具有N个以空格为单位的整数，其中每个整数都小于或等于K。可以保证数组中从1到K的每个整数。任务是找到最小长度的子数组，其中包含所有整数。并打印其开始和结束。请注意，索引从1开始。

例子：

Input         Output
5 3           2 4
1 2 1 3 2

6 4           2 6
2 4 2 3 3 1  

在最近的编程竞赛中，我承担了这项任务。结束了，我没有作弊。我已经使用python 3实现了它：

with open('input.txt') as file:
    N, K = [int(x) for x in file.readline().split()]
    alley = [int(x) for x in file.readline().split()]

trees = {}
min_idx = (1, N)
min_length = N
for i in range(N):
    trees[alley[i]] = i
    if len(trees) == K:
        idx = (min(trees.values())+1, max(trees.values())+1)
        length = idx[1] - idx[0] + 1
        if length < min_length:
            min_idx = idx
            min_length = length
        if min_length == K:
            break


print (str(min_idx[0]) + " " + str(min_idx[1]))

想法是将第i个树的最后位置保存到字典中，如果字典包含所有项目，请检查此子数组是否最小。

第16次测试表明我的算法超出了时间限制，即1秒。我认为，我的算法是O（N），因为它一次跨数组完成，并且映射访问成本为O（1）。

一个人如何加快这种算法？可以降低复杂度吗？还是我对一些需要很多时间的Python的误解？

Answer 1

您的算法很好，但忽略了 的时间len(trees) < K，O(NK)因为每次调用min和max都是O(K)。没有必要打电话，max因为max(trees.values()) == i。处理min比较棘手，但如果您跟踪哪个键对应于最小索引，那么您只能在该键更新时重新计算它。

一个小问题是，您的最后一项if并不总是需要检查。

全面的：

trees = {}
min_idx = (1, N)
min_length = N
first_index = -1
for i in range(N):
    trees[alley[i]] = i
    if len(trees) == K:
        if first_index == -1 or alley[first_index] == alley[i]:
            first_index = min(trees.values())
        idx = (first_index+1, i+1)
        length = idx[1] - idx[0] + 1
        if length < min_length:
            min_idx = idx
            min_length = length
            if min_length == K:
                break