LeetCode 713中等滑动窗口
乘积小于 K 的子数组 图解题解
这道题到底在问什么
正整数数组 nums 与整数 k，统计乘积严格小于 k 的连续子数组个数。
- 输入
- nums=[10,5,2,6], k=100
- 输出
- 8
最优解：一步一步想明白
- 3记住「右扩乘、超了就左缩除、每步加 right−left+1」,下面每一格都在套它。
- 4这一行是数组,全是正整数。窗口从空开始、乘积 prod=1,右指针从左往右一格格扩,我们盯着 prod 和 ans 怎么变。
- 5右指针到第 0 位(值 10),乘进窗口,乘积变成 10。仍然 < k=100,窗口合法。
- 6窗口 [0, 0] 合法。以第 0 位结尾、左端从 0 到 0 的子数组乘积都 < 100,共 1 个,答案加 1,累计 1。
- 7右指针到第 1 位(值 5),乘进窗口,乘积变成 50。仍然 < k=100,窗口合法。
- 8窗口 [0, 1] 合法。以第 1 位结尾、左端从 0 到 1 的子数组乘积都 < 100,共 2 个,答案加 2,累计 3。
- 9右指针到第 2 位(值 2),乘进窗口,乘积变成 100。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。
- 10把左指针右移 1 步、依次除掉移出位,乘积回到 10(<100)。现在窗口是 [1, 2],以第 2 位结尾的合法子数组有 2 个(左端可取 1 到 2),答案加 2,累计 5。
- 11右指针到第 3 位(值 6),乘进窗口,乘积变成 60。仍然 < k=100,窗口合法。
- 12窗口 [1, 3] 合法。以第 3 位结尾、左端从 1 到 3 的子数组乘积都 < 100,共 3 个,答案加 3,累计 8。
- 13右指针到第 4 位(值 1),乘进窗口,乘积变成 60。仍然 < k=100,窗口合法。
- 14窗口 [1, 4] 合法。以第 4 位结尾、左端从 1 到 4 的子数组乘积都 < 100,共 4 个,答案加 4,累计 12。
- 15右指针到第 5 位(值 8),乘进窗口,乘积变成 480。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。
- 16把左指针右移 1 步、依次除掉移出位,乘积回到 96(<100)。现在窗口是 [2, 5],以第 5 位结尾的合法子数组有 4 个(左端可取 2 到 5),答案加 4,累计 16。
- 17右指针到第 6 位(值 3),乘进窗口,乘积变成 288。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。
- 18把左指针右移 2 步、依次除掉移出位,乘积回到 24(<100)。现在窗口是 [4, 6],以第 6 位结尾的合法子数组有 3 个(左端可取 4 到 6),答案加 3,累计 19。
- 19右指针到第 7 位(值 2),乘进窗口,乘积变成 48。仍然 < k=100,窗口合法。
- 20窗口 [4, 7] 合法。以第 7 位结尾、左端从 4 到 7 的子数组乘积都 < 100,共 4 个,答案加 4,累计 23。
- 21右指针到第 8 位(值 4),乘进窗口,乘积变成 192。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。
- 22把左指针右移 2 步、依次除掉移出位,乘积回到 24(<100)。现在窗口是 [6, 8],以第 8 位结尾的合法子数组有 3 个(左端可取 6 到 8),答案加 3,累计 26。
- 23右指针到第 9 位(值 7),乘进窗口,乘积变成 168。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。
- 24把左指针右移 1 步、依次除掉移出位,乘积回到 56(<100)。现在窗口是 [7, 9],以第 9 位结尾的合法子数组有 3 个(左端可取 7 到 9),答案加 3,累计 29。
- 25扫完全程,把每个右端点贡献的「right−left+1」加起来,一共 29 个乘积小于 100 的子数组。右、左指针各只走一遍,O(n)。
⚠️ 容易写错的地方
✗ 错：枚举所有子数组逐个乘
✓ 对：滑动窗口右乘左除
枚举是 O(n²)，窗口复用乘积是 O(n)
✗ 错：忘了 k ≤ 1 的特判
✓ 对：k ≤ 1 直接返回 0
正整数乘积至少为 1，永远不会严格小于 1，没有合法子数组
✗ 错：每步只加 1 个
✓ 对：每步加 right − left + 1 个
以 right 结尾、左端从 left 到 right 的子数组都合法，是一整批不是一个
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
prod = 1
left = ans = 0
for right, x in enumerate(nums):
prod *= x
while prod >= k:
prod //= nums[left]
left += 1
ans += right - left + 1
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int left = 0, ans = 0;
long long prod = 1;
for (int right = 0; right < (int)nums.size(); ++right) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
ans += right - left + 1;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int left = 0, ans = 0;
long prod = 1;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
ans += right - left + 1;
}
return ans;
}
}复杂度
时间
O(n)
左右指针各只前进一遍,每个元素进出窗口各一次
空间
O(1)
只用 left/prod/ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 乘积小于 K 的子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么按「以每个 right 结尾」来数,就不重不漏?+
任何一个连续子数组都有唯一的右端点。我们对每个 right 数出「以它结尾的合法子数组个数」,再把所有 right 的结果加起来,每个子数组恰好被它自己的右端点数到一次,所以不重不漏。
如果数组里可能有 0 或负数怎么办?+
有 0 时乘积会突然变 0、再乘又可能跳变,有负数时乘积正负交替,乘积都不再随窗口长度单调,滑动窗口失效。那种情况要换思路,比如对 0 分段处理,或用前缀积配合其它结构。本题限定正整数,才能稳稳滑窗。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 乘积小于 K 的子数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。