Недавно я боролся со следующей проблемой:
Учитывая массив целых чисел, найдите минимальную (кратчайшую длину) подмассива, которая суммируется как минимум k.
Очевидно, это легко сделать в O (n ^ 2). Я смог написать алгоритм, который решает его в линейном времени для натуральных чисел, но я не могу понять его для целых чисел.
Моя последняя попытка:
def find_minimal_length_subarr_z(arr, min_sum):
found = False
start = end = cur_end = cur_sum = 0
for cur_start in range(len(arr)):
if cur_end <= cur_start:
cur_end, cur_sum = cur_start, arr[cur_start]
else:
cur_sum -= arr[cur_start-1]
# Expand
while cur_sum < min_sum and cur_end < len(arr)-1:
cur_end += 1
cur_sum += arr[cur_end]
# Contract
while cur_end > cur_start:
new_sum = cur_sum - arr[cur_end]
if new_sum >= min_sum or new_sum >= cur_sum:
cur_end -= 1
cur_sum = new_sum
else:
break
if cur_sum >= min_sum and (not found or cur_end-cur_start < end-start):
start, end, found = cur_start, cur_end, True
if found:
return start, end
Например:
[8, -7, 5, 5, 4], 12 => (2, 4)
Однако это не удается для:
[-12, 2, 2, -12, 2, 0], 4
где правильный результат (1, 2)
, но алгоритм не находит его.
Можно ли это сделать в линейном времени (с предпочтительной постоянной пространственной сложностью)?