arrays - 如何在线性时间内为给定的 k 找到至少一次包含所有元素 1 到 k 的最小子数组

Question

假设数组是 {2 4 2 1 5 3 5 3} 并且 k=3。子数组 {2 1 5 3} 包含 1 2 3。

我想知道是否有线性时间算法来解决这个问题。

Answer 1

就在这里：

begin = -1
end = -1
best = 0
new = 1
finalbegin = -1
finalend = -1
for i = 1 to n
    if (new and input[i] >= 1 and input <= k)
        begin = i
        new = 0
    end if
    if (new and (input[i] <= 1 or input[i] >= k) or (i = n))
        if (input[i] <= 1 or input[i] >= k)
            end = i - 1
        else
            end = i
        end if
        new = 1
        if (end - begin >= best)
            finalbegin = begin
            finalend = end
            best = end - begin + 1
        end if
    end if
end for

每当你找到一个新的区间时，你都会检查它是否比已经找到的最佳区间更好。如果是这样，你把它当作新的最好的。如果 begin 和 end 为负数，则空集是解决方案。否则最好的解决方案是