寻找最小窗口大小

Question

给定两个数组A[n]和B[m]，如何找到包含B中所有元素的A中最小的窗口。

我尝试在O(n)时间内解决这个问题，但是我遇到了麻烦。是否有任何众所周知的算法或过程来解决它。

- mousey

---

在这个上下文中，“window”是什么？ - Nikita Rybak

A = {1,3,2,4,5,6,1,2} B = {1,2}，因此最小的窗口是从索引6到7。 - mousey

窗口是否必须包含B的所有元素？顺序重要吗？或者，在您的示例中，位置2..6是否也构成包含B的窗口？ - Ants Aasma

可能是重复的问题，与Google搜索结果：如何找到包含所有搜索关键字的最小窗口？相同。虽然表述略有不同，但实际上是完全相同的问题。 - AnT stands with Russia

Answer 1

如果 m > n，则A不能包含B的所有元素（因此我们有一个O(1)的解决方案）。

否则：

• 创建一个哈希表，将B的元素映射到序列 {0..m-1}（这是O(n)，因为m <= n）。
• 创建一个数组C[m]来计算当前窗口中B成员的出现次数（初始化为0）。

• 创建一个变量z来计算C中0元素的数量（初始化为m）。

• 创建变量s和e来表示当前窗口的开始和结束

• 当e < n时：
  • 如果z不为零，则增加e并更新C和z。O(1)
  • 否则，将此窗口视为可能的解决方案（即如果它是迄今为止的最小值，则存储它），然后增加s并更新C和z。O(1)

可以证明while循环的迭代次数不超过2n。因此整个过程是O(n)，我想。

- Artelius

Answer 2

计数。如果窗口不能被缩小，则称其为“最小化”。即，在增加其左边框或减小其右边框后，它不再是有效的窗口（不包含来自B的所有元素）。在您的示例中有三个：[0,2]，[2,6]，[6,7]。

假设您已经找到了最左边的最小窗口[left，right]。（在您的示例中为[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;
    }
}

这种滑动的实现原理是因为不同的“最小”窗口无法相互包含。

- Nikita Rybak

---

基本上和我的一样，只是你没有指定count的工作方式，而我的代码更难理解。 - Artelius

嗯，如果B中的数字不太大，它可以只是一个数组 :) 但你说得对，这是同样的事情。 - Nikita Rybak

非常感谢Artelius和Nikita。 - mousey