Произведение подмассива меньше k

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

nums = [10, 5, 2, 6], k = 100

8

nums = [1, 2, 3], k = 0

0

Решение

В этой задаче нужно посчитать количество подмассивов, а не найти один лучший.

Полный перебор всех подмассивов требует O(n²) времени и не подходит для больших массивов.

Скользящее окно работает и для подсчета подмассивов. Все элементы положительные. Поэтому при расширении окна вправо произведение не уменьшается, а при сужении слева не увеличивается. Мы можем поддерживать окно, произведение которого строго меньше k.

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

Пусть после всех сужений окно [left..right] валидно, то есть его произведение меньше k.

Тогда все подмассивы, которые заканчиваются в right и начинаются внутри этого окна, тоже валидны:

nums[right]
nums[right-1..right]
nums[right-2..right]
...
nums[left..right]

Почему? Потому что мы берем часть валидного окна и убираем из произведения положительные множители. Произведение от этого не станет больше.

Количество таких подмассивов равно длине окна:

right - left + 1

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

1. Если k <= 1, сразу возвращаем 0.
2. Инициализируем left = 0, product = 1, count = 0.
3. Двигаем правую границу right.
4. Умножаем product на nums[right].
5. Пока product >= k, делим произведение на nums[left] и двигаем left.
6. После сужения окно валидно, и мы добавляем к ответу right - left + 1.

Рассмотрим пример:

nums = [10, 5, 2, 6], k = 100

Идем по массиву:

1. right = 0, окно [10], произведение 10. Добавляем 1.

2. right = 1, окно [10, 5], произведение 50. Добавляем 2: [5] и [10, 5].

3. right = 2, окно [10, 5, 2], произведение 100. Это уже не меньше 100, поэтому нужно сузить окно.

Убираем 10. Окно [5, 2], произведение 10. Добавляем 2.

4. right = 3, окно [5, 2, 6], произведение 60. Добавляем 3.

Итого:

1 + 2 + 2 + 3 = 8

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

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

Каждый элемент один раз входит в произведение и не более одного раза выходит из него. Поэтому оба указателя суммарно делают не больше 2n шагов.

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

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

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

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

Код решения

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

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }
    left := 0
    product := 1
    count := 0
    for right := 0; right < len(nums); right++ {
        product *= nums[right]
        for product >= k {
            product /= nums[left]
            left++
        }
        count += right - left + 1
    }
    return count
}

Итоги

Задача Subarray Product Less Than K - хороший пример того, как скользящее окно используется не только для поиска длины, но и для подсчета всех подходящих подмассивов.

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