713. 乘积小于 K 的子数组

滑动窗口

方法一滑动窗口

滑动窗口右侧负责扩张，左侧收缩。当乘积小于k的时候

nums[right]
nums[right - 1],nums[right]
nums[right - 2],nums[right - 1],nums[right]
...
nums[left],nums[left + 1] ... nums[right - 2],nums[right - 1],nums[right]

这些集合都符合条件，这些数量就是 right - left + 1

参考代码

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans,left,right,mul = 0,0,0,1
        while right < len(nums):
            mul *= nums[right]
            while mul >= k and left <= right:
                mul //= nums[left]
                left += 1
            ans += right - left + 1
            right += 1
        return ans

复杂度分析

时间复杂度O(n)
空间复杂度O(1)