arrays - 查找包含所有元素的最短子数组

Question

假设您有一组数字和另一组数字。您必须以最小的复杂度找到包含所有数字的最短子数组。

数组可以有重复项，我们假设数字集没有。它不是有序的——子数组可以包含任意顺序的数字集。

例如:

Array: 1 2 5 8 7 6 2 6 5 3 8 5
Numbers: 5 7

那么最短的子数组显然是Array[2:5] (python notation)。

此外，如果您想避免出于某种原因(在线算法)对数组进行排序，您会怎么做？

Answer 1

线性时间解的证明

我将写right-extension 表示将范围的右端点增加 1，left-contraction 表示将范围的左端点增加 1 . 这个答案是 Aasmund Eldhuset's answer 的细微变化.这里的区别在于，一旦我们找到最小的 j 使得 [0, j] 包含所有有趣的数字，我们此后只考虑包含所有有趣数字的范围。 (可以这样解释 Aasmund 的答案，但也可以将其解释为允许由于左收缩而丢失一个有趣的数字——一种正确性尚未确定的算法。)

基本思想是，对于每个位置 j，我们将找到在位置 j 结束的最短满足范围，假设我们知道在位置 j-1 结束的最短满足范围。

编辑:修复了基本案例中的一个故障。

基本情况:找到最小的 j' 使得 [0, j'] 包含所有有趣的数字。根据构造，不存在包含所有有趣数字的范围 [0, k < j']，因此我们无需进一步担心它们。现在找到 smallest largest 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[] 是散列/字典(如果涉及的数字很小，则为普通数组)。