最小窗口数组中给定的数字 [英] Minimum Window for the given numbers in an array

问题描述

看到了这个问题，最近：

Saw this question recently:

鉴于2数组，含有一些第一阵列的元件的第二阵列，返回最小窗口包含第二阵列的所有元素的第一阵列中的

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.

例如： 鉴于A = {1,3,5,2,3,1}和B = {1,3,2}

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

输出： 3，5（其中3和5的数组A指数）

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

即使1〜4还包含A的元素，3〜5被返回，因为它包含自其长度比previous范围更低的（（5范围的范围内 - 3）＆其中; （4 - 1））

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

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

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

推荐答案

通过列表迭代的一个简单的解决方案。

A simple solution of iterating through the list.

1. 有一个左和右指针，最初无论是在零
2. 将右指针向前，直到[L..R]包含所有元素（或右侧到达最终退出）。
3. 将左边的指针向前，直到[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.

伪$ C $这种算法℃。

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

这篇关于最小窗口数组中给定的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！