leetcode – 713. Subarray Product Less Than K

本文介绍: leetcode – 713

Given an arr ay of integers nums and an integer k, return the number of c ontiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

Con straints:

1 <= nums.length <= 3 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6

Similar to 2302. Count Subarrays With Score Less Than K, every time when expand in g the win dow, we introduce j - i + 1 new subarrays (with the nums[j] as the end ing element)

Time complexity:

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        cur_prod = 1
        i = 0
        res = 0
        for j in range(len(nums)):
            cur_prod *= nums[j]
            while i <= j and cur_prod >= k:
                cur_prod /= nums[i]
                i += 1
            res += j - i + 1
        return res