Задача с собеседования в Яндекс

Дан массив целых чисел nums и целое число k. Необходимо найти количество смежных подмассивов, произведение элементов которых строго меньше k.

nums = [10, 5, 2, 6], k = 100 
Ответ: 8 
Объяснение: 8 подмассивов удовлетворяют условию: 
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].

Ограничения:
длина от 1 до  3 *10^ 4
значения от 1 до 1000
k от 1 до 10 ^ 6

наш чат алгоритмистов

Решение:
Используем метод скользящего окна с двумя указателями (left и right). product = 1 (текущее произведение), count = 0 (счётчик подмассивов), left = 0 (левый указатель). Для каждого right от 0 до n-1. Умножаем product на nums[right]. Если product >= k, сдвигаем left, деля product на nums[left], пока product снова не станет < k. Добавляем к count количество новых подмассивов: right - left + 1.

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

@algoses