一个遍历列表的简单解决方案。
- 具有左右指针，最初都为零
- 向前移动右指针，直到[L..R]包含所有元素（如果右到达末尾，则退出）。
- 向前移动左指针，直到[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 }}
