剑指 Offer II 009. 乘积小于 K 的子数组 #
- 标签:数组、滑动窗口
- 难度:中等
题目大意 #
给定一个正整数数组 nums
和一个整数 k
。
要求:找出该数组内乘积小于 k
的连续子数组的个数。
解题思路 #
滑动窗口求解。
设定两个指针:left
、right
,分别指向滑动窗口的左右边界,保证窗口内所有数的乘积 product
都小于 k
。
-
一开始,
left
、right
都指向0
。 -
向右移动
right
,将最右侧元素加入当前子数组乘积product
中。 -
如果
product >= k
,则不断右移left
,缩小滑动窗口,并更新当前乘积值product
直到product < k
。 -
累积答案个数 += 1,继续右移
right
,直到right >= len(nums)
结束。 -
输出累积答案个数。
代码 #
|
|