Код Senior Скользящее окно обновлено
Все подмассивы с заданной суммой
Условие
Массив положительных чисел. Верни все непрерывные подмассивы, сумма которых равна target, в порядке появления.
Что проверяют тесты
находит все
нет подходящих
весь массив
пустой вход
Как подойти
Окно работает только потому, что числа положительные: сумма растёт при расширении и убывает при сжатии, значит монотонна. С отрицательными пришлось бы брать префиксные суммы. Перекрывающиеся результаты получаются сами: после найденного мы продолжаем сжимать, а не начинаем заново.
Подсказки: 2
- Окно переменной длины: расширяем вправо, сжимаем слева при переборе суммы.
- Подмассивы могут перекрываться - сжатие продолжается и после найденного.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными