我有一个数组和一个数字 N。
数组可以填充数字 0,1,2,3....N。
例如,arr={1,0,2,3,1,0,2,4,3,1,0,2,4,3,0,0,0} //给定 N=4
我必须找到包含所有数字 1,2,...N 的最小长度子数组。
例如,上面数组的答案应该是 {1,0,2,3,1,0, 2,4,3,1 ,0,2,4,3,0,0,0}// length=4 , 并且索引 start=6,end=9, //0 基于
上述问题的一个可能答案是 {1,0,2, 3,1,0,2,4 ,3,1,0,2,4,3,0,0,0},但由于其长度为 5,它被拒绝了..如果有一个以上长度最短的子数组,答案应该是第 1 次出现。或者,如果数组不包含 1,2..N 之间的一个或多个数字,则答案是“未找到子数组”。
这是我的python代码。它在某些情况下会产生错误的答案(我不知道)......如果有人能告诉我我做错了什么。
shortlen=2000001 //initialise to INFINITY
shortstart=0
matchln=len(match) //match is the array containing integers
while(i<matchln):
if(match[i]>0):
leng=0
pos=[0]*n // array to keep status of found integers
j=i
start=i
sums=0
while(j<matchln and sums!=n):
if(match[j]>0):
if(pos[match[j]-1]==0): //only update status if the integer is not marked previously.
pos.pop(match[j]-1)
pos.insert(match[j]-1,1) //(match[j]-1) becuz array indexing is from 0.
sums+=1
j+=1
leng=j-i
if(j==matchln and sums!=n): // if the loop terminated,without marking all integers,that means we shouldn't proceed.
break
if(leng<shortlen): //if the length calculated is smaller then existing,then update it.
shortlen=leng
shortstart=start
i+=1