难度: Medium
给定一个正整数数组 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 * 1041 <= nums[i] <= 10000 <= k <= 106注意：本题与主站 713 题相同：https://leetcode-cn.com/problems/subarray-product-less-than-k/
运行时间: 81 ms
内存: 18.1 MB
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if not nums:
return 0
if k <= 1:
return 0
# 滑窗 + 前缀和
n = len(nums)
window_product = 1
left = 0
right = 0
answer = 0
while right < n:
window_product *= nums[right]
right += 1
# 缩小窗口
while window_product >= k:
# 缩小操作
window_product //= nums[left]
left += 1
# 更新答案
answer += right - left
return answer
该题解采用了滑动窗口的方法来寻找所有乘积小于k的子数组。初始化两个指针left和right指向数组的起始位置，以及一个变量window_product来保存窗口内数字的乘积。向右移动right指针，扩大窗口，并更新window_product。如果window_product达到或超过了k，就逐渐移动left指针，缩小窗口，直到window_product小于k。每次当窗口的乘积有效（小于k）时，可以确定以right-1为结尾的子数组数量为right-left，因为每一个以right-1为结束点的子数组都有一个不同的起始点，这些起始点从left到right-1。因此，每次迭代中，都将这个长度加到结果answer中。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if not nums:
return 0
if k <= 1:
return 0
n = len(nums)
window_product = 1
left = 0
right = 0
answer = 0
while right < n:
window_product *= nums[right] # 扩大窗口并更新乘积
right += 1
while window_product >= k: # 当窗口内乘积不符合条件时
window_product //= nums[left] # 缩小窗口
left += 1
answer += right - left # 计算当前有效窗口的子数组数量
return answer
在 k 小于等于 1 的情况下，由于数组元素都是整数，最小的正整数是 1，乘积中包含任何正整数都会使得乘积不小于 1。因此，不存在任何非空子数组的乘积小于 1。直接返回 0 是因为根据题目的定义和数学逻辑，不可能有符合条件的子数组。
滑动窗口通过动态调整窗口的大小（通过移动左右指针），可以有效地探索所有可能的子数组。当增加窗口右边界（即向右扩展窗口）可能导致新的子数组产生时，每次窗口的乘积有效时（即小于 k），则可以确认以当前右边界-1（right-1）为结束点的所有子数组都符合条件。通过逐步移动左指针，直到窗口内的乘积小于 k，确保了每次都重新计算从新的左指针开始到右指针-1为止的所有子数组。这种方法确保了从每个可能的起始点到每个可能的终点的所有子数组都被考虑到，从而没有遗漏任何一个乘积小于 k 的子数组。
移动左指针来缩小窗口是一种有效的方式来降低窗口内的乘积，因为这种方法可以逐步减少乘积，直到窗口内的乘积再次小于 k。如果考虑跳过某些元素，可能会错过一些有效的子数组，因为即使当前元素使得乘积超标，该元素左侧或右侧可能存在许多符合条件的子数组。通过逐步移动左指针，我们可以确保考虑到从当前右指针开始的所有可能的子数组，而不会遗漏任何应该被计算的组合。