Задача: 713. Subarray Product Less Than K
Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.
Пример:
Input: nums = [10,5,2,6], k = 100
Output: 8
👨💻 Алгоритм:
1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива.
2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.
3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями.
😎 Решение:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int product = 1, count = 0, left = 0;
for (int right = 0; right < nums.size(); right++) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
count += right - left + 1;
}
return count;
}👉Новости 👉База вопросов