查找包含所有数字的最小长度子阵列

Question

文件输入。txt由两行组成：第一行是整数N空格，然后是整数K（1 ≤ N、 K级≤ 250000). Second有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

使整数数组计数[K]，用零填充。
保留一些变量-左索引L，右索引R（如您的idx[0]和idx[1]），零计数Z。
设置L和R为1，增量计数[A[1]]，设置Z为K-1

移动R，递增计数[A[1]]，如果零条目被更新，则递减Z，直到Z变为0，此时子数组[L..R]包含从到K的所有值

现在移动L，递减离开窗口的值的计数条目。如果某个条目变为0，则增加Z。当Z变为非零时，停止移动L并再次移动R。

当R达到N并且L停止时，过程结束。最小长度从有效（R-L1）对最小

Example run for your [1 2 1 3 2]

Move R
1 0 0  Z=2
1 1 0  Z=1
2 1 0  Z=1
2 1 1  Z=0
Move L
1 1 1  Z=0
1 0 1  Z=1 Stop moving L, check previous L,R pair 2,4
Move R
1 1 1  Z=0
move L
9 1 1  Z=1 Stop moving L, check previous L,R pair 3,5

Answer 2

你的算法很好，但是忽略了len（tree）的时间

一个次要的问题是，您的最后一个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