713. Subarray Product Less Than K
Difficulty: Medium
Related Topics: Array, Two Pointers
Your are given an array of positive integers nums
.
Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is 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.
Note:
0 < nums.length <= 50000
.*0 < nums[i] < 1000
.*0 <= k < 10^6
.
Solution
Language: Python3
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k==0:
return 0
rep=0
cur=1
l=0
r=0
while r<len(nums):
if nums[r]>=k:
rep+=(1+r-l)*(r-l)//2
r+=1
l=r
else:
while r<len(nums) and nums[r]*cur<k:
cur*=nums[r]
r+=1
if r==len(nums):
n=r-l
rep+=(1+n)*n//2
else:
if l<r:
rep+=r-l
cur//=nums[l]
l+=1
else:
cur=1
return rep