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

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

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

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