Минимальный подмассив с суммой

Постановка задачи

target = 7, nums = [2, 3, 1, 2, 4, 3]

2

target = 4, nums = [1, 4, 4]

1

target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]

0

Решение

Наивное решение перебирает все возможные подмассивы и считает сумму для каждого. Даже при инкрементальном подсчете это требует O(n²), что слишком медленно для 10⁵ элементов.

Главное свойство задачи: все числа в массиве положительные. Это гарантирует монотонность суммы окна:

• при сдвиге правой границы right вправо сумма только увеличивается;
• при сдвиге левой границы left вправо сумма только уменьшается.

Благодаря этому можно применить динамическое скользящее окно с двумя указателями.

Идея решения:

Поддерживаем окно [left..right] и текущую сумму его элементов windowSum.

1. Двигаем right вправо и прибавляем nums[right] к windowSum.
2. Как только windowSum >= target, текущее окно становится подходящим:
   • обновляем минимальную длину: minLength = min(minLength, right - left + 1);
   • сдвигаем left вправо и вычитаем nums[left] из суммы, проверяя, можно ли сделать подходящее окно еще короче.
3. Повторяем сужение окна, пока windowSum >= target. Когда сумма станет меньше target, снова продолжаем двигать правую границу.

Основные шаги:

1. Инициализируем left = 0, windowSum = 0 и minLength = infinity.
2. Проходим указателем right по всему массиву.
3. Добавляем nums[right] в windowSum.
4. Пока windowSum >= target:
   • обновляем minLength = min(minLength, right - left + 1);
   • вычитаем nums[left] из windowSum;
   • увеличиваем left на 1.
5. Если подходящее окно не было найдено (minLength не изменился), возвращаем 0, иначе возвращаем minLength.

Рассмотрим пример target = 7, nums = [2, 3, 1, 2, 4, 3].

1. Расширяем окно вправо, пока сумма не станет не меньше target. Получаем [2, 3, 1, 2], сумма равна 8, длина равна 4.

2. Сужаем окно слева. Убираем 2, сумма становится 6 < 7. Окно перестало подходить, поэтому снова расширяем его вправо.

3. Добавляем 4: окно [3, 1, 2, 4], сумма равна 10.

4. Сужаем окно слева. Убираем 3: окно [1, 2, 4], сумма равна 7, длина равна 3. Это новый минимум.

5. Сумма все еще не меньше target, сужаем дальше. Убираем 1: окно [2, 4], сумма равна 6.

6. Добавляем 3: окно [2, 4, 3], сумма равна 9.

7. Сужаем до [4, 3]. Сумма равна 7, длина равна 2. Это минимальная длина, при дальнейшем сужении сумма станет меньше target.

Итог: ответ равен 2.

Оценка сложности

Временная сложность

Указатель right проходит по массиву один раз, а указатель left также двигается только вправо и проходит по массиву не более одного раза. Каждый элемент входит в окно и покидает его максимум один раз.

Итоговая временная сложность: O(n).

Пространственная сложность

Мы храним только сумму окна, границы и минимальную длину. Дополнительная память не зависит от размера входных данных.

Пространственная сложность: O(1).

Код решения

Приведем код решения.

import "math"
 
func minSubArrayLen(target int, nums []int) int {
left := 0
windowSum := 0
minLength := math.MaxInt32
 
    for right := 0; right < len(nums); right++ {
        windowSum += nums[right]
        for windowSum >= target {
            length := right - left + 1
            minLength = min(minLength, length)
            windowSum -= nums[left]
            left++
        }
    }
 
    if minLength == math.MaxInt32 {
        return 0
    }
    return minLength
 
}
 

Итоги

Задача Minimum Size Subarray Sum - базовый пример динамического скользящего окна, где нужно найти минимальный подходящий подмассив.

1. Суть алгоритма: расширяем окно вправо, пока сумма меньше target, а затем сужаем его слева, пока условие windowSum >= target сохраняется, обновляя минимальную длину.
2. Эффективность:
   • Временная сложность: O(n), так как оба указателя проходят массив не более одного раза.
   • Пространственная сложность: O(1), алгоритм использует фиксированное число переменных.
3. Граничные случаи:
   • Подходящего подмассива нет (сумма всех элементов меньше target): возвращаем 0.
   • Один элемент больше или равен target: минимальная длина равна 1.
4. Оптимальное решение: скользящее окно находит ответ за один проход O(n) благодаря монотонности суммы положительных чисел.