跳至主要內容

0713. 乘积小于 K 的子数组

ITCharge大约 2 分钟

0713. 乘积小于 K 的子数组open in new window

  • 标签:数组、滑动窗口
  • 难度:中等

题目链接

题目大意

描述:给定一个正整数数组 numsnums 和整数 kk

要求:找出该数组内乘积小于 kk 的连续的子数组的个数。

说明

  • 1nums.length31041 \le nums.length \le 3 * 10^4
  • 1nums[i]10001 \le nums[i] \le 1000
  • 0k1060 \le k \le 10^6

示例

  • 示例 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:滑动窗口(不定长度)

  1. 设定两个指针:leftleftrightright,分别指向滑动窗口的左右边界,保证窗口内所有数的乘积 windowproductwindow\underline{}product 都小于 kk。使用 windowproductwindow\underline{}product 记录窗口中的乘积值,使用 countcount 记录符合要求的子数组个数。
  2. 一开始,leftleftrightright 都指向 00
  3. 向右移动 rightright,将最右侧元素加入当前子数组乘积 windowproductwindow\underline{}product 中。
  4. 如果 windowproductkwindow\underline{}product \ge k,则不断右移 leftleft,缩小滑动窗口长度,并更新当前乘积值 windowproductwindow\underline{}product 直到 windowproduct<kwindow\underline{}product < k
  5. 记录累积答案个数加 11,继续右移 rightright,直到 rightlen(nums)right \ge len(nums) 结束。
  6. 输出累积答案个数。

思路 1:代码

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

        size = len(nums)
        left = 0
        right = 0
        window_product = 1
        
        count = 0
        
        while right < size:
            window_product *= nums[right]

            while window_product >= k:
                window_product /= nums[left]
                left += 1

            count += (right - left + 1)
            right += 1
            
        return count

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(1)O(1)