Почему это работает
- Все числа положительные, поэтому у длинного окна сумма больше. Если окно хорошее, то и все окна длиннее с тем же правым краем хорошие, но короче они не станут: проверять стоит только то, что получится при сужении.
- Длина записывается во время сужения, на каждом хорошем окне, а сужаем, пока сумма не станет меньше target. Так для каждого right измеряется самое короткое хорошее окно, которое кончается на нём.
- Убирать число на left безопасно: окно от left до right было хорошим и уже измерено, а окно с тем же left и следующим right кончалось бы правее, то есть было бы только длиннее.
Сложность
Время O(n): right проходит каждое число один раз, left — не больше одного раза, поэтому внутренний цикл за всё время выполняется не больше n раз. Память O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗