0713. 乘积小于K的子数组

0713. 乘积小于K的子数组 #

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

题目大意 #

给定一个正整数数组 nums和整数 k

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

解题思路 #

滑动窗口求解。

设定两个指针:leftright,分别指向滑动窗口的左右边界,保证窗口内所有数的乘积 window_product 都小于 k。使用 window_product 记录窗口中的乘积值,使用 count 记录符合要求的子数组个数。

  • 一开始,leftright 都指向 0

  • 向右移动 right,将最右侧元素加入当前子数组乘积 window_product 中。

  • 如果 window_product >= k ,则不断右移 left,缩小滑动窗口长度,并更新当前乘积值 window_product 直到 window_product < k

  • 记录累积答案个数 += 1,继续右移 right,直到 right >= len(nums) 结束。

  • 输出累积答案个数。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
本站总访问量  次  |  您是本站第  位访问者