algorithm - 数组中给定数字的最小窗口

Question

最近看到这个问题:

给定 2 个数组，第二个数组包含第一个数组的一些元素，返回第一个数组中包含第二个数组的所有元素的最小窗口。

例如:给定 A={1,3,5,2,3,1} 和 B={1,3,2}

输出: 3 , 5 (其中 3 和 5 是数组 A 中的索引)

即使范围 1 到 4 也包含 A 的元素，但返回范围 3 到 5 因为它包含 因为它的长度小于之前的范围 ( ( 5 - 3 ) < ( 4 - 1 ) )

我已经设计了一个解决方案，但我不确定它是否能正常工作并且效率不高。

为问题提供有效的解决方案。提前致谢

Answer 1

遍历列表的简单解决方案。

1. 有一个左右指针，最初都为零
2. 向前移动右指针，直到 [L..R] 包含所有元素(如果右指针到达末尾则退出)。
3. 向前移动左指针，直到 [L..R] 不包含所有元素。查看 [L-1..R] 是否比当前最佳短。

这显然是线性时间。您只需跟踪 B 的每个元素在子数组中的数量，以检查子数组是否是一个潜在的解决方案。

该算法的伪代码。

size = bestL = A.length;
needed = B.length-1;
found = 0; left=0; right=0;
counts = {}; //counts is a map of (number, count)
for(i in B) counts.put(i, 0);

//Increase right bound
while(right < size) {
    if(!counts.contains(right)) continue;
    amt = count.get(right);
    count.set(right, amt+1);
    if(amt == 0) found++;
    if(found == needed) {
        while(found == needed) {
            //Increase left bound
            if(counts.contains(left)) {
                amt = count.get(left);
                count.set(left, amt-1);
                if(amt == 1) found--;
            }
            left++;
        }
        if(right - left + 2 >= bestL) continue;
        bestL = right - left + 2;
        bestRange = [left-1, right] //inclusive
    }
}