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

Saw this question recently:

最近看到这个问题：

Given 2 arrays, the 2nd array containing some of the elements of the 1st array, return the minimum window in the 1st array which contains all the elements of the 2nd array.

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

Eg : Given A={1,3,5,2,3,1} and B={1,3,2}

例如：给定A = {1,3,5,2,3,1}，B = {1,3,2}

Output : 3 , 5 (where 3 and 5 are indices in the array A)

输出：3,5（其中3和5是数组A中的索引）

Even though the range 1 to 4 also contains the elements of A, the range 3 to 5 is returned Since it contains since its length is lesser than the previous range ( ( 5 - 3 ) < ( 4 - 1 ) )

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

I had devised a solution but I am not sure if it works correctly and also not efficient.

我设计了一个解决方案，但我不确定它是否正常工作，也没有效率。

Give an Efficient Solution for the problem. Thanks in Advance

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

1 个解决方案

#1

A simple solution of iterating through the list.

迭代列表的简单解决方案。

Have a left and right pointer, initially both at zero
有一个左右指针，最初都是零
Move the right pointer forwards until [L..R] contains all the elements (or quit if right reaches the end).
向前移动右指针，直到[L..R]包含所有元素（如果右边到达末尾，则退出）。
Move the left pointer forwards until [L..R] doesn't contain all the elements. See if [L-1..R] is shorter than the current best.
向前移动左指针，直到[L..R]不包含所有元素。查看[L-1..R]是否短于当前最佳值。

This is obviously linear time. You'll simply need to keep track of how many of each element of B is in the subarray for checking whether the subarray is a potential solution.

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

Pseudocode of this algorithm.

该算法的伪代码。

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
    }
}

#1