如何高效计算积小于k的连续子数组个数？

Question

如何高效计算积小于k的连续子数组个数是算法设计中的经典问题。给定一个正整数数组和一个目标值k，我们需要找出所有乘积小于k的连续子数组。暴力解法时间复杂度为O(n^2)，效率较低。如何优化到线性或近线性时间复杂度？可以采用滑动窗口（双指针）技术，维护一个动态窗口，跟踪当前子数组的乘积。当乘积小于k时扩展右边界，否则收缩左边界。同时，利用数学性质：若以某个元素结尾的子数组满足条件，则其所有前缀也满足条件，从而避免重复计算。此方法时间复杂度为O(n)，空间复杂度为O(1)。但需要注意边界情况，例如k<=1时无有效子数组。如何处理这些细节以确保算法鲁棒性？

Answer 1

1. 问题概述

在算法设计中，计算积小于k的连续子数组个数是一个经典问题。给定一个正整数数组和目标值k，我们需要找出所有乘积小于k的连续子数组。暴力解法的时间复杂度为O(n^2)，效率较低。为了优化性能，可以采用滑动窗口（双指针）技术。

滑动窗口的核心思想是维护一个动态窗口，跟踪当前子数组的乘积。当乘积小于k时扩展右边界，否则收缩左边界。利用数学性质：若以某个元素结尾的子数组满足条件，则其所有前缀也满足条件，从而避免重复计算。

1.1 关键词

• 滑动窗口
• 双指针
• 连续子数组
• 时间复杂度
• 边界情况

2. 算法分析

滑动窗口方法通过维护一个窗口来高效解决问题。以下是具体步骤：

1. 初始化两个指针left和right，分别指向数组的起始位置。
2. 初始化一个变量product，用于存储当前窗口内元素的乘积。
3. 遍历数组，逐步扩展right指针，并更新product。
4. 如果product >= k，收缩left指针，直到product < k。
5. 对于每个满足条件的窗口，统计以right指针结尾的有效子数组个数。

这种方法的时间复杂度为O(n)，空间复杂度为O(1)。

2.1 边界情况处理

需要特别注意以下边界情况：

情况	描述	解决方案
k <= 1	没有有效子数组，因为所有正整数乘积至少为1。	直接返回0。
数组为空	输入数组为空时，结果应为0。	在算法开始前检查数组长度。
数组元素包含0	虽然题目要求正整数数组，但需确保代码对异常输入的鲁棒性。	提前验证输入数据的有效性。

3. 实现与示例

以下是基于Python的实现代码：

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1
    left = 0
    count = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count
    

例如，输入数组[10, 5, 2, 6]，k=100，输出为8。

3.1 流程图

以下是滑动窗口算法的流程图：