给定一个正整数数组 nums和整数 k
。
请找出该数组内乘积小于 k
的连续的子数组的个数。
例如:nums = [10,5,2,6]
, k = 100
输出:8
解释:8 个乘积小于 100 的子数组分别为:[10], [5], [2], [6], [10,5], [5,2], [2,6], [10,5,2]
。
- 关键词连续子数组
- 采用滑动窗口,但本题与
长度最小的子数组
不同的是需要求个数,而不是最小长度,这就需要对符合条件的子数组进行累加。 - 在初始化左右窗口之前,利用数组内元素都是正整数的性质,如果
k
为0
或1
,说明没有符合条件的子数组,直接返回0
。
if target <= 1:
return 0
- 初始化窗口与
长度最小的子数组
相同,只不过需要计算的是乘积和而不是累加和。
while multi >= target:
multi /= nums[left]
left += 1
ans += right - left + 1
- 与
长度最小的子数组
不同的是,ans
的累加需要放在while
循环之后,因为当我们找到临界状态的left
之后(即[left, right]
区间内乘积小于target
,而[left - 1, right]
乘积大于等于target
),直接就可以计算出在当前rigth
位置下所有符合条件的子数组的个数,所有子数组如下:[[left, right]],[left + 1, right],...,[right, right]
,一共有right - left + 1
个。 - 时间复杂度:
O(n)
,空间复杂度:O(1)
。