Задачи
August 6, 2023
Минимальный размер подмассива сумм
Дан массив положительных целых чисел nums и положительное целое число target.
Необходимо вернить минимальную длину подмассива сумма элементов которого больше или равна target. Если такого подмассива не существует, верните 0.
target = 7, nums = [2,3,1,2,4,3] Output: 2
Разбор
Воспользуемся методом 2х указателей. Правый указатель - для конца текущего подмассива, левый указатель для начала подмассива. Далее мы можем делать оптимальные перемещения этих указателей таким образом, чтобы сумма подмассива была равна или больше target. Также будем минимизировать размер этого подмассива.
Алгоритм
- Инициализируем левый указатель left = 0, а также сумму элементов sum = 0;
- В цикле по исходному массиву добавляем текущий элемент в sum.
- Вложенный цикл пока sum >= target. В этом вложенном цикле находим размер подмассива, далее двигаем левый указатель вправо и пробуем уменьшить найденный подмассив.
- На выходе возвращаем результат.
Детали реализации смотрите ниже.