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 题目约束根据 题解文档 中的 Note0 nums.length 50000数组非空最多 5 万个元素0 nums[i] 1000每个元素都是小于 1000 的正整数0 k 10^6K 最小可以为 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]、[left1..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 变量语义变量含义res累计的合法子数组个数left/right滑动窗口的左右边界均为下标索引prod当前窗口[left, right)内所有元素的乘积初始为 1空窗口的乘积注意代码中的窗口是左闭右开区间[left, right)prod始终表示下标从left到right-1这段元素的乘积。3.2 三个分支的执行逻辑外层循环以left len(nums)为终止条件每次迭代进入以下三种情况之一扩展右边界贪婪扩展当right len(nums)且prod*nums[right] k时将nums[right]乘入prodright右移。这一步尽量把窗口向右拉长直到再乘一个元素就会越过 K。窗口收缩的特殊情况left right如果窗口内乘积已经不小于 K且窗口长度为 0左右指针重合说明当前单个元素nums[left]本身就 K。此时把left和right同时右移一位跳过该元素。这正是 题解文档 中强调的「类似[100]这种情况」窗口内乘积等于 K或大于 K左窗口等于右窗口需要左右窗口同时右移。统计并收缩左边界否则说明窗口[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永远不成立会不断走入分支 2left right时双指针同时右移最终返回 0。仓库测试用例{[]int{1, 2, 3}, 0}期望输出 0验证了这一行为。四、示例逐步推演以[10, 5, 2, 6], k 100为例以下按源码逻辑手动推演与 测试文件 中第一个用例一致用于验证算法正确性步骤leftrightprod命中分支res10010扩展乘nums[0]10020150扩展乘nums[1]5030250prod*nums[2]100不小于 k → 统计res 2prod50/105241210扩展乘nums[2]2251360扩展乘nums[3]6261460right 越界 → 统计res 3prod60/512572412统计res 2prod12/2678346统计res 1prod6/6189441left len(nums)循环结束8最终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代码会误入分支 3res 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 个用例输入numsk期望输出覆盖点[10, 5, 2, 6]1008题目标准示例[10, 9, 10, 4, 3, 8, 3, 3, 6, 2, 10, 10, 9, 3]1918长数组、窗口频繁收缩[]1000空数组边界[1, 2, 3]00k 0 边界测试通过go test运行t.Fatalf会在结果不符时输出input / expected / got三者信息便于定位。这些用例覆盖了文档强调的边界分支空输入、k0以及常规滑动窗口路径。6.2 在仓库中的运行方式仓库根目录提供 gotest.sh 一键测试脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.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 是一道极具代表性的滑动窗口计数题核心要点有三利用正整数乘积的单调性维护合法窗口避免枚举子数组以右端点固定计数窗口合法时直接累加right - left实现 O(1) 摊销统计显式处理「单元素乘积 ≥ K」的退化窗口左右指针重合时同步右移保证算法在所有输入下状态合法。本仓库在 题解文档 中给出了完整思路在 源码实现 与 测试文件 中给出了可运行、可验证的完整闭环值得作为滑动窗口入门的模板题反复研读。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 713 Subarray Product Less Than K 题解：滑动窗口统计乘积小于 K 的连续子数组（Go 实现）
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 题目约束根据 题解文档 中的 Note0 nums.length 50000数组非空最多 5 万个元素0 nums[i] 1000每个元素都是小于 1000 的正整数0 k 10^6K 最小可以为 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]、[left1..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 变量语义变量含义res累计的合法子数组个数left/right滑动窗口的左右边界均为下标索引prod当前窗口[left, right)内所有元素的乘积初始为 1空窗口的乘积注意代码中的窗口是左闭右开区间[left, right)prod始终表示下标从left到right-1这段元素的乘积。3.2 三个分支的执行逻辑外层循环以left len(nums)为终止条件每次迭代进入以下三种情况之一扩展右边界贪婪扩展当right len(nums)且prod*nums[right] k时将nums[right]乘入prodright右移。这一步尽量把窗口向右拉长直到再乘一个元素就会越过 K。窗口收缩的特殊情况left right如果窗口内乘积已经不小于 K且窗口长度为 0左右指针重合说明当前单个元素nums[left]本身就 K。此时把left和right同时右移一位跳过该元素。这正是 题解文档 中强调的「类似[100]这种情况」窗口内乘积等于 K或大于 K左窗口等于右窗口需要左右窗口同时右移。统计并收缩左边界否则说明窗口[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永远不成立会不断走入分支 2left right时双指针同时右移最终返回 0。仓库测试用例{[]int{1, 2, 3}, 0}期望输出 0验证了这一行为。四、示例逐步推演以[10, 5, 2, 6], k 100为例以下按源码逻辑手动推演与 测试文件 中第一个用例一致用于验证算法正确性步骤leftrightprod命中分支res10010扩展乘nums[0]10020150扩展乘nums[1]5030250prod*nums[2]100不小于 k → 统计res 2prod50/105241210扩展乘nums[2]2251360扩展乘nums[3]6261460right 越界 → 统计res 3prod60/512572412统计res 2prod12/2678346统计res 1prod6/6189441left len(nums)循环结束8最终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代码会误入分支 3res 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 个用例输入numsk期望输出覆盖点[10, 5, 2, 6]1008题目标准示例[10, 9, 10, 4, 3, 8, 3, 3, 6, 2, 10, 10, 9, 3]1918长数组、窗口频繁收缩[]1000空数组边界[1, 2, 3]00k 0 边界测试通过go test运行t.Fatalf会在结果不符时输出input / expected / got三者信息便于定位。这些用例覆盖了文档强调的边界分支空输入、k0以及常规滑动窗口路径。6.2 在仓库中的运行方式仓库根目录提供 gotest.sh 一键测试脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.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 是一道极具代表性的滑动窗口计数题核心要点有三利用正整数乘积的单调性维护合法窗口避免枚举子数组以右端点固定计数窗口合法时直接累加right - left实现 O(1) 摊销统计显式处理「单元素乘积 ≥ K」的退化窗口左右指针重合时同步右移保证算法在所有输入下状态合法。本仓库在 题解文档 中给出了完整思路在 源码实现 与 测试文件 中给出了可运行、可验证的完整闭环值得作为滑动窗口入门的模板题反复研读。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
