Кратчайший подмассив с суммой ≥ target: задача по Алгоритмы

Условие

Все числа положительные. Длина кратчайшего непрерывного подмассива с суммой не меньше target. Нет такого - 0.

Примеры

minSubArrayLen(7, [2, 3, 1, 2, 4, 3]) // 2
minSubArrayLen(11, [1, 1, 1]) // 0
minSubArrayLen(4, [4]) // 1

Как подойти

Окно переменной длины. Работает только на положительных числах: с отрицательными сумма не монотонна и сжатие теряет смысл - там нужны префиксные суммы. Это первый вопрос интервьюера.

Подсказки: 2

Расширяй окно вправо, сжимай влево, пока условие ещё выполняется.
Ответ фиксируется внутри сжатия, а не после него.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Решить в тренажёре

Предыдущий вопрос

Максимум гласных в окне

Следующий вопрос

Самая короткая подстрока с k различными

Урок по теме

Паттерн: Скользящее окно

Термины по теме

Скользящее окно

Ещё по теме «Скользящее окно»

Все вопросы модуля