Сложность: medium
Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.
Пример:
Input: nums = [10,5,2,6], k = 100
Output: 8
👨💻 Алгоритм:
1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива.
2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.
3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями.
😎 Решение:
func numSubarrayProductLessThanK(_ nums: [Int], _ k: Int) -> Int {
if k <= 1 {
return 0
}
var product = 1
var count = 0
var left = 0
for right in 0..<nums.count {
product *= nums[right]
while product >= k {
product /= nums[left]
left += 1
}
count += right - left + 1
}
return count
}Ставь 👍 и забирай 📚 Базу знаний