寻找最小的窗口

Question

鉴于两个数组A[n]和B[m],我怎么能找到最小的窗口A,其中包含的所有元素B.

我试图在O(n)时间内解决这个问题,但我遇到了问题.是否有任何熟知的算法或程序来解决它.

Answer 1

如果窗口无法缩小，我们将其称为“最小”窗口。即，在增加其左边框或减少右边框后，它不再是有效窗口（不包含 B 中的所有元素）。您的示例中有三个： [0, 2]、[2, 6]、[6, 7]

假设您已经找到最左边的最小窗口 [左，右]。（在您的示例中为 [0, 2]）现在我们将其向右滑动。

// count[x] tells how many times number 'x'
// happens between 'left' and 'right' in 'A'
while (right < N - 1) {
    // move right border by 1
    ++right;
    if (A[right] is in B) {
        ++count[A[right]];
    }

    // check if we can move left border now
    while (count[A[left]] > 1) {
        --count[A[left]];
        ++left;
    }

    // check if current window is optimal
    if (right - left + 1 < currentMin) {
        currentMin = right - left + 1;
    }
}

这种滑动之所以有效，是因为不同的“最小”窗口不能相互包含。