线性时间解的证明

我将写“ 右延伸” 表示将范围的右端点增加1，将“ 左收缩” 表示将范围的左端点增加1。此答案是Aasmund
Eldhuset答案的略有变化。此处的区别在于，一旦我们找到最小的j，使得[0，j]包含所有感兴趣的数字，此后，我们将仅考虑包含所有感兴趣的数字的范围。（有可能以此方式解释Aasmund的答案，但也有可能将其解释为允许由于左收缩而丢失一个有趣的数字，该算法的正确性尚待确定。）

基本思想是，对于每个位置j，我们都将找到终止于位置j的最短满足范围，因为我们知道终止于位置j-1的最短满足范围。

编辑： 修复了基本情况下的故障。

基本情况：找到最小的j’，使[0，j’]包含所有有趣的数字。通过构造，不可能存在包含所有有趣数字的范围[0，k
<j’]，因此我们无需进一步担心它们。现在找到 最小的
最大i，使[i，j’]包含所有有趣的数字（即，保持j’固定）。这是在位置j’处结束的最小满足范围。

为了找到以任意位置j结尾的最小满足范围，我们可以将以j-1结尾的最小满足范围右扩展1个位置。该范围也可能包含所有有趣的数字，尽管它可能不是最小长度。
我们已经知道这是一个令人满意的范围，这一事实意味着我们不必担心将范围向后“向后”扩展到左侧，因为这只会在最小长度上扩大范围（即使解决方案更糟）。
我们需要考虑的唯一操作是左收缩，它保留了包含所有有趣数字的属性。因此，在保持此属性的同时，应将范围的左端点尽可能提前。当无法再执行左收缩操作时，我们得到的最小长度满足范围以j结尾（因为进一步的左收缩显然不能使范围再次满足），我们完成了。

由于我们对每个最右边的位置j执行此操作，因此我们可以对所有最右边的位置取最小长度范围，以找到整体的最小值。这可以使用嵌套循环来完成，其中j在每个外循环循环中前进。显然，j前进了1
n倍。由于在任何时间点我们都只需要先前范围j的最佳范围的最左位置，因此我们可以将其存储在i中，并随即进行更新。i从0开始，始终在<= j <=
n，并且仅向前进1，这意味着它最多可以向n前进。i和j最多前进n次，这意味着该算法是线性时间。

在下面的伪代码中，我将两个阶段组合成一个循环。只有在达到所有有趣数字的阶段，我们才尝试收缩左侧：

# x[0..m-1] is the array of interesting numbers.
# Load them into a hash/dictionary:
For i from 0 to m-1:
    isInteresting[x[i]] = 1

i = 0
nDistinctInteresting = 0
minRange = infinity
For j from 0 to n-1:
    If count[a[j]] == 0 and isInteresting[a[j]]:
        nDistinctInteresting++
    count[a[j]]++

    If nDistinctInteresting == m:
        # We are in phase 2: contract the left side as far as possible
        While count[a[i]] > 1 or not isInteresting[a[i]]:
            count[a[i]]--
            i++

        If j - i < minRange:
            (minI, minJ) = (i, j)

count[]并且isInteresting[]是哈希/字典（如果涉及的数字很小，则为纯数组）。