713. 乘积小于 K 的子数组

🎯 问题描述（来源于LeetCode）

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

说明：

子数组必须连续。
数组元素均为正整数。
如果 k <= 1，由于所有正整数乘积 ≥ 1，所以没有子数组满足条件，直接返回 0。

示例：

示例 1：

1
2
3

输入: 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：

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

💻 解题思路

思路：滑动窗口（双指针）

算法步骤

若 k <= 1，直接返回 0（因为所有元素为正，乘积至少为 1，不可能小于 1）。
初始化左指针 left = 0，当前乘积 prod = 1，答案 ans = 0。
遍历右指针 right 从 0 到 n-1：
- 将 nums[right] 乘入 prod。
- 当 prod >= k 时，不断将左指针元素从乘积中移除（prod //= nums[left]），并将 left 右移，直到 prod < k。
- 此时，以 right 为右端点的所有子数组（左端点从 left 到 right）都满足乘积 < k，数量为 right - left + 1，累加到 ans。
返回 ans。

代码实现

from typing import List

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

📊 性能分析

时间复杂度： $O(n)$ ，每个元素最多被左右指针各访问一次。
空间复杂度： $O(1)$ ，仅使用常数个变量。

思考

该解法是滑动窗口的标准应用，利用数组元素均为正整数的性质，窗口乘积随右端点扩展而单调递增，因此可以安全地移动左指针来收缩窗口。关键点在于：每次满足条件时，直接累加以当前右端点结尾的所有合法子数组数量（right - left + 1），因为左端点可以从 left 到 right 任意选择，且这些子数组的乘积都 < k。这种计数方法比枚举所有子数组更高效。代码简洁，边界条件 k <= 1 的处理也很必要。