⚡️ Хитрая задача на Python: кратчайший подмассив с суммой ≥ K (O(n))
Задача. Дан массив A (могут быть отрицательные) и K. Найти минимальную длину подмассива с суммой ≥ K. Если нет — вернуть -1.
Подвох. С отрицательными числами не работает двухуказательную. Решение — префиксные суммы + монотонная дека.
Идея.
Пусть P[i] — префиксная сумма до i. Нам нужно минимизировать i - j при условии P[i] - P[j] ≥ K.
Храним индексы j в деке так, что значения P[j] строго возрастают:
- Пока текущий P[i] − P[deque[0]] ≥ K — обновляем ответ и выкидываем голову (нашли короткий кандидат).
- Пока P[i] ≤ P[deque[-1]] — выкидываем хвост (бессмысленные, более «жирные» префиксы).
- Затем добавляем i.
Сложность: каждый индекс заходит/вылетает из деки по разу → O(n).
Короткая реализация
from collections import deque
from math import inf
from typing import List
def shortest_subarray_at_least_k(A: List[int], K: int) -> int:
P = [0]
for x in A: P.append(P[-1] + x)
dq, ans = deque(), inf # dq хранит индексы префиксов, их суммы возрастают
for i, s in enumerate(P):
while dq and s - P[dq[0]] >= K:
ans = min(ans, i - dq.popleft())
while dq and P[dq[-1]] >= s:
dq.pop()
dq.append(i)
return -1 if ans is inf else ans
# Примеры
if __name__ == "__main__":
print(shortest_subarray_at_least_k([2, -1, 2], 3)) # 3 (весь массив)
print(shortest_subarray_at_least_k([1, 2, 3, 4], 6)) # 2 (3+3 нет, но 2+4 или 3+4 длина 2)
print(shortest_subarray_at_least_k([84, -37, 32, 40, 95], 167)) # 3
Почему это работает?
Если у нас есть два индекса j1