乘积小于 K 的子数组

标签: 数组 滑动窗口

难度: 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 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106

Submission

运行时间: 78 ms

内存: 18.0 MB

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        count = 0
        left = 0
        prod = 1

        for right in range(len(nums)):
            prod *= nums[right]

            while prod >= k and left <= right:
                prod //= nums[left]
                left += 1

            count += right - left + 1

        return count

Explain

这个题解采用了滑动窗口的策略来找出所有乘积小于 k 的子数组。首先，定义一个变量 prod 来存储当前窗口内所有元素的乘积，和一个计数器 count 来统计符合条件的子数组数目。遍历数组 nums，使用一个右指针 right 表示当前窗口的右边界。对于每一个新的 right，将 nums[right] 乘到 prod 上。如果 prod 大于或等于 k，则移动左指针 left 直到 prod 小于 k。每次找到有效的窗口后，可以通过 right-left+1 计算出新添加的子数组数量，因为每扩展一次右边界，就会增加从 left 到 right 的所有连续子数组。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0  # 当 k 小于等于 1 时，没有有效的子数组

        count = 0  # 计数符合条件的子数组数量
        left = 0  # 左指针
        prod = 1  # 用于计算当前窗口内所有元素的乘积

        for right in range(len(nums)):
            prod *= nums[right]  # 将当前元素乘到 prod 上

            while prod >= k and left <= right:
                prod //= nums[left]  # 如果 prod 大于等于 k，移动左指针，并更新 prod
                left += 1

            count += right - left + 1  # 计算包括当前右指针元素的新子数组数量

        return count  # 返回总数

Explore

当k小于等于1时，无论数组中的元素如何，任何非空子数组的乘积都至少为1（因为数组元素都是正整数）。因此，不能存在乘积小于1的子数组，所以直接返回0是合理的。

滑动窗口的目标是探索所有可能的子数组，而右指针向右移动时增加元素至prod，可以帮助我们持续扩展当前的窗口，从而发现新的符合条件的子数组。如果仅在左指针移动时更新prod，我们将无法有效地利用之前的计算结果，因每次右指针扩展都可能产生新的符合条件的子数组。

每当右指针right向右移动并包含一个新元素时，我们可以形成新的子数组，这些子数组的结束点都是新的right位置，起始点从left到right。例如，如果left为2而right为5，那么新增的子数组包括[2,5]、[3,5]、[4,5]和[5]共(right-left+1)个。这样计算可以快速统计每扩展一次右边界时新增的子数组数量。

如果数组中存在0，那么任何包含0的子数组的乘积都将是0，这显然小于k（假设k>1）。在遇到0的情况下，prod会变成0，我们需要重置prod为1并将左指针移动到0的下一个位置，因为包含0的任何子数组都不需要进一步考虑乘积是否满足条件。