LeetCode LCR 009. 乘积小于 K 的子数组
题目描述
题意分析
统计正整数数组中乘积严格小于
k的非空连续子数组数量。按左右端点区分子数组，即使内容相同但位置不同，也分别计数。元素至少为一，所以扩张区间不会减小乘积，移除左端也不会增大乘积。
k <= 1时任何非空区间都不合法；当前代码通过允许窗口缩空统一处理这一边界。
解法：滑动窗口维护乘积
核心思路
[!blue]
固定右端
j，如果以i为左端的窗口乘积已经小于k，那么从i到j之间任意更靠右的位置开始，乘积只会更小或相同，也都合法。因此找到最靠左的合法起点后，就能一次计入j - i + 1个以当前右端结尾的子数组。用
s保存当前窗口乘积，初值为一。加入新元素后，如果乘积达到或超过k，就持续除掉左端元素并右移i，直到恢复严格小于，或者窗口已经为空。为什么左端不用回退？一个起点被排除时，它对应的乘积已经不小于
k；以后右端继续加入至少为一的元素，乘积不会下降，所以这个旧起点仍不可能重新合法。当前左端以前的起点都已被安全排除，之后的起点则都合法，正好形成可以批量计数的连续范围。先收缩、后计数。若单个元素就超标，或者
k <= 1，窗口可能缩到i == j + 1，贡献自然为零。空窗口乘积回到一，所以循环还要保留i <= j的边界条件，不能只看乘积是否仍超标。移出的数一定是当前乘积的因子，整除能准确还原剩余窗口。按题目
k <= 10^6、元素不超过一千的范围，收缩后的乘积小于k，下一次扩张的乘积仍小于10^9；空窗口扩张也只加入一个元素。代码不会无限累积全数组乘积，Java 使用long，Go 的计算在本题范围内也能由 32 位整数容纳。
解题步骤
- 初始化乘积
s = 1、左端i = 0、答案为零。- 右端每前进一步，乘入当前元素。
- 当窗口非空且乘积不小于
k时，除掉左端元素并右移左端，必要时连续收缩。- 收缩结束后，将
j - i + 1加入答案；窗口为空时这一项为零。- 扫描全部右端后返回总数。
代码实现
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
// s 是乘积，初值取乘法单位元 1；用 long 兜住中间的一次乘法。
long s = 1;
int answer = 0;
for (int i = 0, j = 0; j < nums.length; ++j) {
s *= nums[j];
// i <= j 这个守卫覆盖 k <= 1 与单个元素超标的情形。
while (i <= j && s >= k) {
s /= nums[i++];
}
// 收缩完成后 i 才是临界左端点，此时一次性计入 j - i + 1 个子数组。
answer += j - i + 1;
}
return answer;
}
}
func numSubarrayProductLessThanK(nums []int, k int) int {
s := 1
answer, i := 0, 0
for j, x := range nums {
s *= x
for i <= j && s >= k {
s /= nums[i]
i++
}
answer += j - i + 1
}
return answer
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(n)$，每个元素至多乘入和除出一次，每个右端只做一次批量计数。
- 辅助空间复杂度：$O(1)$，只维护指针、乘积和计数。
关键点总结
[!green]
- 正整数使乘积对扩张不减，已排除的左端不会重新合法。
- 固定右端后，合法起点是一个连续范围，窗口长度就是新增数量。
- 当前实现允许缩成空窗口，用边界守卫处理
k <= 1和单元素超标。- 乘积从一开始，每次移出通过精确整除维护。
易错点总结
[!yellow]
- 条件要求严格小于，乘积等于
k也必须继续收缩。- 乘积不能初始化为零，否则窗口状态永远无法正确恢复。
- 缩窗只做一次可能仍超标，必须反复判断。
- 在收缩前计入窗口长度，会把不合法的起点算进答案。
- 空窗口乘积为一，
k <= 1时仍不满足数值条件，所以不能去掉当前写法的i <= j守卫。- 输入含零或负数时，精确除法和单调性前提改变，不能直接复用这份正整数窗口。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 同样利用正数建立窗口单调性，原题求最短长度，本题通过合法后缀长度累计数量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！