我有以下问题需要解决:
给定一组整数,例如{1,3,2},以及一个随机整数数组,例如
[1, 2, 2, -5, -4, 0, 1, 1, 2, 2, 0, 3,3]
找到包含集合中所有值的最短连续子数组。如果找不到子数组,则返回一个空数组。
结果:[1, 2, 2, 0, 3]
或者
[1, 2, 2, -5, -4, 3, 1, 1, 2, 0], {1,3,2}
。
结果:[3, 1, 1, 2]
我已经尝试了以下设置,我的第二个循环似乎有问题。我不确定我需要更改什么:
def find_sub(l, s):
i = 0
counts = dict()
end = 0
while i < len(s):
curr = l[end]
if curr in s:
if curr in counts:
counts[curr] = counts[curr] + 1
else:
counts[curr] = 1
i += 1
end += 1
curr_len = end
start = 0
for curr in l:
if curr in counts:
if counts[curr] == 1:
if end < len(l):
next_item = l[end]
if next_item in counts:
counts[next_item] += 1
end += 1
else:
counts[curr] -= 1
start += 1
else:
start += 1
if (end - start) < curr_len:
return l[start:end]
else:
return l[:curr_len]
最佳答案
您正在使用双指针方法,但只移动两个索引一次 - 直到找到第一个匹配项。您应该重复 move right - move left
模式以获得最佳索引间隔。
def find_sub(l, s):
left = 0
right = 0
ac = 0
lens = len(s)
map = dict(zip(s, [0]*lens))
minlen = 100000
while left < len(l):
while right < len(l):
curr = l[right]
right += 1
if curr in s:
c = map[curr]
map[curr] = c + 1
if c==0:
ac+=1
if ac == lens:
break
if ac < lens:
break
while left < right:
curr = l[left]
left += 1
if curr in s:
c = map[curr]
map[curr] = c - 1
if c==1:
ac-=1
break
if right - left + 1 < minlen:
minlen = right - left + 1
bestleft = left - 1
bestright = right
return l[bestleft:bestright]
print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 0, 3, 3], {1,3,2}))
print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1,3,2}))
>>[2, -5, -4, 3, 1]
>>[2, 1, 0, 3]
关于python - 查找包含集合中所有值的最短连续子数组的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56000424/