LeeCode 713 乘积小于k的子数组

2023-06-05,,

LeeCode 713

题目描述:

给你一个整数数组 nums 和一个整数 k ,请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

标签: 双指针、滑动窗口

建立模型

枚举子数组的右端点right,左端点从left=0开始,mul记录当前子数组[left, right]的乘积。如果当前子数组乘积大于等于k,那么移动子数组的左端点直到满足条件;如果当前子数组的乘积小于k,则当前子数组的所有包含right端点的连续子数组都符合要求(个数为right - left + 1)。

如果left > right,则表示当前right端点的值大于等于k,需要跳过即此时 right - left + 1 = 0
要求包含右端点的连续子数组,是为了避免重复统计。

编码实现

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

LeeCode 713 乘积小于k的子数组的相关教程结束。

《LeeCode 713 乘积小于k的子数组.doc》

下载本文的Word格式文档,以方便收藏与打印。