⚡️ Хитрая задача на 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 < j2 и P[j1] ≥ P[j2], то j1 никогда не даст более короткого валидного подмассива, чем j2, — его можно выбросить (инвариант монотонной деки).