企业官网建设流程全解析

LeetCode 713 Subarray Product Less Than K 题解：滑动窗口统计乘积小于 K 的连续子数组（Go 实现）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode 713 题解文档 为主体，结合本仓库 LeetCode-Go 中的源码实现与测试用例，深入讲解如何用滑动窗口（Sliding Window）算法统计「乘积严格小于 K」的连续子数组个数。读完本文，你将掌握这道经典滑动窗口题的完整思路、Go 实现细节、边界情况处理（如单个元素乘积恰好等于 K）以及仓库内的测试验证方法。

一、题目理解与约束条件

1.1 题目原文

给定一个正整数数组nums，统计并输出所有（连续的）子数组中，所有元素乘积小于 K的子数组个数。

示例：

Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

注意[10, 5, 2]的乘积恰好为 100，不满足「严格小于 K」的条件，因此不计入结果。

1.2 题目约束

根据 题解文档 中的 Note：

• 0 < nums.length <= 50000：数组非空，最多 5 万个元素；
• 0 < nums[i] < 1000：每个元素都是小于 1000 的正整数；
• 0 <= k < 10^6：K 最小可以为 0。

这些约束决定了算法必须满足 O(n) 级别的复杂度才能高效处理 50000 长度的输入，同时也意味着当k = 0时（所有元素都为正数，乘积恒大于 0），答案必然为 0。

1.3 题目大意

题解文档中的中文概括：给出一个数组，要求输出符合条件的窗口数，条件是窗口中所有数字乘积小于 K。这是典型的滑动窗口应用场景——在一个连续区间上维护动态变化的乘积，并统计满足约束的区间个数。

二、核心解题思路：滑动窗口 + 右端点定长计数

2.1 为什么可以用滑动窗口

由于nums[i]全部为正整数，乘积具有单调性：窗口向右扩展时乘积只增不减，左边界向右收缩时乘积只减不增。这种单调性使得我们可以用双指针（left、right）维护一个始终满足prod < k的合法窗口，而无需枚举所有子数组。

2.2 经典计数技巧：以右端点为基准

每当我们固定右端点right，并保证窗口[left, right]内乘积小于 K 时，以right结尾的合法子数组个数恰好为right - left。这是因为左端点可以从left一直取到right-1（即right - left个起点），对应的子数组为[left..right]、[left+1..right]、……、[right-1..right]。

这样累加每个右端点贡献的子数组数量，即可得到总数，时间复杂度 O(n)。

三、仓库源码实现逐行解析

本仓库中的实现位于 713. Subarray Product Less Than K.go，函数签名与 LeetCode 平台一致：

func numSubarrayProductLessThanK(nums []int, k int) int { if len(nums) == 0 { return 0 } res, left, right, prod := 0, 0, 0, 1 for left < len(nums) { if right < len(nums) && prod*nums[right] < k { prod = prod * nums[right] right++ } else if left == right { left++ right++ } else { res += right - left prod = prod / nums[left] left++ } } return res }

3.1 变量语义

注意代码中的窗口是左闭右开区间[left, right)：prod始终表示下标从left到right-1这段元素的乘积。

3.2 三个分支的执行逻辑

外层循环以left < len(nums)为终止条件，每次迭代进入以下三种情况之一：

1. 扩展右边界（贪婪扩展）：当right < len(nums)且prod*nums[right] < k时，将nums[right]乘入prod，right右移。这一步尽量把窗口向右拉长，直到再乘一个元素就会越过 K。
2. 窗口收缩的特殊情况（left == right）：如果窗口内乘积已经不小于 K，且窗口长度为 0（左右指针重合），说明当前单个元素nums[left]本身就 >= K。此时把left和right同时右移一位，跳过该元素。这正是 题解文档 中强调的「类似[100]这种情况」：窗口内乘积等于 K（或大于 K），左窗口等于右窗口，需要左右窗口同时右移。
3. 统计并收缩左边界：否则说明窗口[left, right)是合法窗口，累加res += right - left，然后用除法把nums[left]从prod中移除（prod = prod / nums[left]），left右移，继续寻找以新的left为起点的合法窗口。

3.3 边界处理：空数组与 k = 0

• 函数开头if len(nums) == 0直接返回 0，防御空输入；
• 当k = 0时，由于所有元素均为正数，prod*nums[right] < 0永远不成立，会不断走入分支 2（left == right时双指针同时右移），最终返回 0。仓库测试用例{[]int{1, 2, 3}, 0}期望输出 0，验证了这一行为。

四、示例逐步推演：以[10, 5, 2, 6], k = 100为例

以下按源码逻辑手动推演（与 测试文件 中第一个用例一致），用于验证算法正确性：

最终res = 8，与题目示例输出一致。推演过程印证了「以右端点为基准累加right - left」的正确性：每次统计得到的 2、3、2、1 分别对应以nums[2]、nums[3]、nums[3]（收缩后）、nums[3]（再次收缩后）为右端点的合法子数组组合。

五、边界情况专项分析

5.1 单个元素乘积恰好等于 K（文档重点强调的场景）

题解文档 专门指出需要单独处理类似[100]（假设k = 100）的情况：

• 此时prod*nums[right] = 100不小于k，无法进入分支 1；
• 且窗口为空（left == right），进入分支 2，左右指针同时右移，跳过该元素。

如果缺少分支 2，代码会误入分支 3：res += right - left会把 0 计入（此时right - left = 0，恰好不产生错误计数，但prod / nums[left]会得到 1），随后left右移但right不动，导致right < left的非法状态，破坏后续统计。因此分支 2 是保证双指针始终满足right >= left的关键防御逻辑。

5.2 k = 0 与空数组

• k = 0时答案恒为 0（正数乘积不可能小于 0），源码通过分支 2 的空窗口跳转自然得出 0；
• 空数组时函数开头直接返回 0。

六、测试验证：仓库内的用例设计与运行方式

6.1 测试用例结构

仓库为每道题配套了标准测试文件，本题的测试位于 713. Subarray Product Less Than K_test.go，采用para713/ans713结构组织输入与期望输出，共覆盖 4 个用例：

测试通过go test运行，t.Fatalf会在结果不符时输出input / expected / got三者信息便于定位。这些用例覆盖了文档强调的边界分支（空输入、k=0）以及常规滑动窗口路径。

6.2 在仓库中的运行方式

仓库根目录提供 gotest.sh 一键测试脚本，其核心命令为：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该脚本一次性对./leetcode/...下所有题解包执行测试并生成合法的覆盖率文件 coverage.txt（脚本注释中说明：旧写法逐个包追加-coverprofile会生成带重复mode: atomic头的文件，被新版 Codecov 解析器判定为 0% 覆盖率，因此改为 Go 1.10+ 的单次多包输出方式）。单独验证本题可运行：

go test -v -run Test_Problem713 ./leetcode/0713.Subarray-Product-Less-Than-K

仓库的整体质量指标（100% 测试覆盖率、runtime beats 100%）正是建立在每道题均配有上述结构统一的测试文件基础之上。

七、复杂度分析

• 时间复杂度：O(n)。left和right各最多移动n次（left在最坏情况下遍历整个数组，right同样至多到达数组末尾），每次迭代只做常数次乘法/除法与比较，因此整体线性；
• 空间复杂度：O(1)。仅使用res、left、right、prod四个变量，不依赖额外存储结构。

相比暴力枚举所有子数组并逐一计算乘积的 O(n²) 做法，滑动窗口利用正数乘积的单调性将复杂度降为线性，可以轻松应对nums.length <= 50000的约束。

八、小结

LeetCode 713 是一道极具代表性的滑动窗口计数题，核心要点有三：

1. 利用正整数乘积的单调性维护合法窗口，避免枚举子数组；
2. 以右端点固定计数：窗口合法时直接累加right - left，实现 O(1) 摊销统计；
3. 显式处理「单元素乘积 ≥ K」的退化窗口（左右指针重合时同步右移），保证算法在所有输入下状态合法。

本仓库在 题解文档 中给出了完整思路，在 源码实现 与 测试文件 中给出了可运行、可验证的完整闭环，值得作为滑动窗口入门的模板题反复研读。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go