【leetcode】剑指 Offer II 009. 乘积小于 K 的子数组（滑动窗口、双指针）

剑指 Offer II 009. 乘积小于 K 的子数组

给定一个正整数数组 nums 和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2:

输入: nums = [1,2,3], k = 0
输出: 0

提示:

• $1<=nums.length<=3\ast 10^4$
• $1<=nums[i]<=1000$
• $0<=k<=10^6$

题解

这题和 【leetcode】剑指 Offer II 008. 和大于等于 target 的最短子数组（滑动窗口，双指针） 比较相似。

滑动窗口枚举

不出意外，这个又超时了

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        def multiply(num_list):  # 累乘
            res = 1
            for num in num_list:
                res *= num
            return res
        num = 0
        for size in range(1, len(nums) + 1):
            for i in range(len(nums) + 1 - size):
                sum_window = multiply(nums[i: i + size])
                if sum_window < k:
                    num += 1
        return num

双指针

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        length = len(nums)
        num = 0
        left = 0
        sum = 1
        for right, value in enumerate(nums):
            sum *= value
            while sum >= k and left <= right:
                sum /= nums[left]
                left += 1
            num += right - left + 1
        return num

以 nums = [10,5,2,6], k = 100 为例：

right = 0
[10] 5  2  6    sum < k    num += 0-0+1 = 1  [10]
right = 1
[10  5] 2  6    sum < k    num += 1-0+1 = 2  [5]  [10 5]
right = 2
[10  5  2] 6    sum = k
 10 [5  2] 6    sum < k    num += 2-1+1 = 2  [2]  [5 2]
right = 3 
 10 [5  2  6]   sum < k    num += 3-1+1 = 3  [6]  [2 6]  [5 2 6]