数组中给定数字的最小窗口
数组中给定数字的最小窗口
提问于 2010-08-01 16:26:26
最近看到这个问题：
给定两个数组，第二个数组包含第一个数组的一些元素，返回第一个数组中包含第二个数组所有元素的最小窗口。
Eg :给出了A={1,3,5,2,3,1}和B={1,3,2}
输出: 3，5(其中3和5是数组A中的索引)
尽管范围1到4也包含A的元素，但由于其长度小于前一个范围( (5-3)<(4-1 ) )，所以返回范围3至5
我设计了一个解决方案，但我不确定它是否正确，也没有效率。
给出了这个问题的有效解决方案。提前谢谢
回答 1
Stack Overflow用户
回答已采纳
发布于 2010-08-01 16:39:50
迭代列表的简单解决方案。
- 有一个左指针和右指针，初始位置为0，
- 将右指针向前移动，直到L.R包含所有元素(或者如果右到末尾就退出)。
- 将左指针向前移动，直到L.R不包含所有元素为止。看看L1.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
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3382757
复制相关文章
相似问题
腾讯云开发者
