713. 乘积小于 K 的子数组

题目链接：713. 乘积小于 K 的子数组

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

核心思考：滑动窗口与组合计数

这道题求的是满足特定条件的连续子数组的数量，并且数组元素均为正整数（保证了乘积的单调递增性）。这完美契合滑动窗口的应用场景。

1. 窗口扩展与收缩

• 右指针 right 负责不断向右移动，将新元素纳入窗口，并累乘其值到状态变量 product 中，代表区间尝试扩张。
• 左指针 left 负责在窗口状态打破约束（即区间乘积 product >= k）时启动收缩。通过循环不断向右步进并除以移出窗口的元素值，直至窗口内的乘积再次严格小于 k，或者左右指针重合。

2. 子数组数量的数学映射

这道题最绝妙的地方在于对“数量”的统计。
当确定了一个满足条件、长度为 $L$ 的滑动窗口 [left, right) 时，必须以该窗口最右侧元素为结尾的合法子数组数量，正好等于这个窗口的长度 $L$。
换句话说，每当右指针合法向右挪动一次，为最终答案贡献的合法子数组新增数量，就是当前这个合法窗口的宽度。因为代码中 right 已经提前完成了 + 1 操作，使得当前窗口区间为 [left, right-1]，所以其准确的计算长度即为 right - left。（这就省去了常规滑动窗口模板中常见的 right - left + 1 操作）。

解题思路 (Python)

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        l = len(nums)
        left = right = 0
        product = 1
        ans = 0
        while right < l:
            product *= nums[right]
            right += 1
            while product >= k and right > left:
                product //= nums[left]
                left += 1
            ans += (right - left) # 应该是right-left+1个 因为right已经自增过了所以这里不用+1了
        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组 nums 的长度。虽然存在嵌套的 while 循环，但右指针 right 和左指针 left 各自最多只会从头到尾遍历数组一次（即每个元素最多分别进、出窗口各一次）。因此，分摊到每个元素上的操作次数是常数级别的，整体时间开销严格为线性。
• 空间复杂度：$O(1)$。算法在执行全程中仅维护了 left、right、product 和 ans 几个常数级别的变量标识状态，没有开辟任何与数据量级正相关的新内存空间。