LeetCode-Go 题解精讲930. Binary Subarrays With Sum前缀和 频率计数Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 930 题「Binary Subarrays With Sum和为 S 的二进制子数组」展开结合 LeetCode-Go 仓库中该题的 README 文档 与 Go 源码实现系统讲解「前缀和 频率计数」这一核心解法如何把「子数组和等于 S」的计数问题转化为「前缀和差值等于 S」的查表问题并通过freq数组在 O(n) 时间内完成统计。读完本文你将掌握这类「子数组和定值计数」问题的通用套路并能看懂、复现并独立推演仓库中 930 题的完整实现与测试用例。题目理解统计和为 S 的非空子数组个数题目原文见 README.mdIn an array A of 0s and 1s, how many non-empty subarrays have sum S?数组A中只有0和1两种元素需要统计「所有非空子数组连续的一段中元素之和恰好等于S」的子数组个数。示例示例 1输入: A [1,0,1,0,1], S 2 输出: 4说明符合条件和为 2的 4 个子数组分别为[1,0,1,0,1] → A[0..2] 101 [1,0,1,0,1] → A[1..3] 0101 [1,0,1,0,1] → A[2..4] 101 [1,0,1,0,1] → A[0..4] 10101题目大意用一句话概括给定一个只包含0和1的数组问有多少个和为S的连续子数组。数据范围与约束原文档给出的约束条件如下A.length 300000 S A.lengthA[i]的取值只能是0或1约束中两个关键点直接影响解法设计数组长度可达 30000O(n²) 的暴力枚举枚举所有[i, j]区间并求和在最坏情况下需要约 9 亿次操作不可接受必须设计 O(n) 或 O(n log n) 的算法元素非 0 即 1元素均为非负数前缀和具有单调不减的性质这为后续的滑动窗口变体提供了空间。核心思路把「子数组和」转化为「前缀和之差」从滑动窗口到前缀和原文档将本题归类为滑动窗口题目其解题思路原文是这道题也是滑动窗口的题目。不断的加入右边的值直到总和等于 S。[i,j]区间内的和可以等于[0,j]的和减去[0,i-1]的和。这里蕴含了本题最关键的数学转化。定义前缀和prefix[0] 0 prefix[k] A[0] A[1] ... A[k-1] 前 k 个元素之和那么任意子数组A[i..j]闭区间的和可以表示为sum(A[i..j]) prefix[j1] - prefix[i]题目要求sum(A[i..j]) S即prefix[j1] - prefix[i] S ⇔ prefix[i] prefix[j1] - S于是问题转化为遍历到当前位置j时历史上出现过多少个前缀和等于prefix[j1] - S每出现一个就对应一个以j结尾的合法子数组。这正是「前缀和 哈希计数」解法的本质。频率数组 freq 的含义原文档对freq的说明在 freq 中不断的记下能使得和为 sum 的组合方法数例如 freq[1] 2代表和为 1 有两种组合方法可能是 1 和 10 或者 01这道题只管组合总数没要求输出具体的组合对。即freq[k]记录的是「到当前扫描位置为止前缀和恰好等于k的出现次数」。由于前缀和的值域为[0, n]n为数组长度前缀和最大不会超过元素个数可以直接用定长整型数组实现不需要哈希表freq : make([]int, len(A)1)数组下标即前缀和的值长度为len(A)1恰好覆盖值域0..len(A)。为什么 freq[0] 初始化为 1实现中在遍历开始前执行了freq[0] 1这一步的含义是前缀和0在「空数组」这个起点上已经出现了一次。它对应着「整个数组从开头到当前位置j的和恰好等于S」这一情况——此时prefix[i] prefix[0] 0即i 0子数组从数组头开始。如果没有这个初始化所有「以A[0]开头且和为S」的子数组都会被漏掉计数会不完整。从源码实现看这也是整个算法正确性的关键一笔。源码级实现讲解仓库中的核心实现在 930. Binary Subarrays With Sum.go函数签名与逐行逻辑如下func numSubarraysWithSum(A []int, S int) int { freq, sum, res : make([]int, len(A)1), 0, 0 freq[0] 1 for _, v : range A { t : sum v - S if t 0 { // 总和有多余的需要减去 t除去的方法有 freq[t] 种 res freq[t] } sum v freq[sum] fmt.Printf(freq %v sum %v res %v t %v\n, freq, sum, res, t) } return res }逐行拆解行号代码作用freq, sum, res : make([]int, len(A)1), 0, 0初始化频率数组长度n1、当前前缀和、结果计数器分配 O(n) 空间freq[0] 1空前缀的和0出现一次保证「从数组头开始的子数组」不被漏计t : sum v - St即prefix[j1] - S也就是需要「从历史前缀和中减去」的目标值等价于上文的prefix[i]目标值if t 0 { res freq[t] }只有当t 0时才可能命中历史前缀和累加freq[t]种组合核心计数步骤sum v; freq[sum]更新当前前缀和并将其出现次数 1供后续位置查表维护频率表fmt.Printf(...)打印调试信息freq、sum、res、t便于观察算法运行过程这里有一个细节值得注意t 0的判断。因为数组元素非负前缀和单调不减所以对任意历史位置i都有prefix[i] prefix[j1]即prefix[i] - (prefix[j1] - S) S 0恒成立反过来若t 0则意味着目标前缀和小于 0而前缀和永远非负必然没有历史命中。因此t 0是一个合法的剪枝判断也是数组索引安全的保证避免freq越界访问负下标。同时可以看到t的计算发生在sum更新之前用的是「加入v之后的前缀和」去减S这与等式prefix[j1] - prefix[i] S完全对应。手工推演以仓库测试用例为例推演示例一A [1,0,1,0,1]S 2仓库测试用例给出的期望答案是4。我们逐步推演步骤vt sumv-S命中res 累计sum 更新freq 更新初始化———00freq[0]11101-2 -1无01freq[1]12010-2 -1无01freq[1]23111-2 0freq[0]112freq[2]14020-2 0freq[0]122freq[2]25121-2 1freq[1]243freq[3]1最终res 4与预期一致。第 3 步命中的是子数组A[0..2]前缀和 0 → 2第 4 步命中A[1..3]前缀和 1 → 2第 5 步命中的freq[1] 2对应两个以j 4结尾的合法子数组A[2..4]与A[0..4]分别对应历史前缀和prefix[2] 1和prefix[0] 1。推演示例二全零数组 A [0,0,0,0,0]S 0这也是仓库测试文件中的用例期望答案是15。全零数组的任意非空子数组和都为 0因此答案应为5 4 3 2 1 15。用算法推演步骤vt命中 freq[0]res 累计freq[0] 更新初始化———01100-0 011220023330036440041055005156每一步的res freq[0]恰好把「以当前位置结尾的所有全零子数组」全部计入最终15与期望一致。这个极端用例很好地验证了freq[0] 1初始化的正确性若缺少该初始化结果会变成10漏掉 5 个从数组头开始的子数组。测试验证仓库测试用例分析仓库为该题提供了完整的单元测试见 930. Binary Subarrays With Sum_test.go。测试文件采用本仓库统一的「para/ans」结构体模式组织用例type para930 struct { s []int k int } type ans930 struct { one int }para930描述输入数组s与目标值kans930描述期望输出三个用例分别是输入数组S期望输出用例设计意图[1,0,1,0,1]24题目官方示例含 0 元素覆盖「中间跨 0」的子数组[0,0,0,0,0]015全零边界所有子数组和均为 0检验计数上限与freq[0]初始化[1,0,1,1,1,1,0,1,0,1]24长数组混合 0/1覆盖连续 1 与间隔 0 的多种组合第二个用例全零数组 S0是最有价值的边界测试它同时检验了「空子数组是否被误计」结果 15 恰好是非空子数组总数n(n1)/2和「前缀和 0 的计数是否正确累积」。从测试运行输出也可以看出每个用例都会打印输入与调用numSubarraysWithSum的结果进行比对【input】:[1 0 1 0 1] 【output】:4 【input】:[0 0 0 0 0] 【output】:15 【input】:[1 0 1 1 1 1 0 1 0 1] 【output】:4复杂度分析时间复杂度O(n)其中n为数组长度。仅需一次从左到右的遍历每次迭代执行常数次操作计算t、查表、更新freq。相比暴力枚举 O(n²)在n 30000的约束下这是决定性的优化。空间复杂度O(n)。freq数组长度为n1用于存储各个前缀和的出现次数。若将freq换为哈希表空间复杂度在平均情况下可视为 O(n) 但常数更大由于前缀和值域已知且连续定长数组是更优选择也避免了哈希冲突。延伸思考相关解法与题目家族滑动窗口视角与本题的特殊性原文档将本题归为「滑动窗口的题目」这里补充说明为什么典型的双指针滑动窗口需要额外处理经典的双指针滑动窗口如 76. Minimum Window Substring适用于「窗口和满足单调性」的场景但本题数组包含 0S 0时窗口和不会随窗口扩张而严格递增单纯的「快慢指针 收缩」无法正确统计例如全零数组中任意窗口和都为 0双指针无法区分窗口边界。因此仓库实现选择了「前缀和 频率计数」这一更稳妥的通用解法——它天然兼容 0 元素。同一思路的变体若题目改为「恰好等于 K 的连续子数组个数」且元素可为任意整数前缀和 哈希表仍是标准解法只是前缀和不再单调t 0的剪枝失效需无条件查表对应经典题 560. Subarray Sum Equals K若题目要求「和不超过 S 的子数组个数」而非「恰好等于 S」则可利用非负数组前缀和单调的性质配合二分或双指针在 O(n) 内求解若要求「和等于 S 且长度最短/最长」则可在同一前缀和框架下额外记录「某个前缀和首次/最后出现的位置」。本仓库的配套资源若希望继续深入该题与相关解法可在仓库中查阅930 题 README本文依据的原始文档题目原文、示例与解题思路简述930 题 Go 实现含逐行注释与调试输出的完整可运行代码930 题测试用例三个覆盖常规、边界与混合场景的用例560. Subarray Sum Equals K同一「前缀和 计数」思路在一般整数数组上的推广滑动窗口题解汇总目录仓库主页对各类题目解题思路的分类索引。小结LeetCode 930 的核心价值在于一个干净利落的思想跃迁不直接枚举子数组而是通过前缀和把「子数组和等于 S」翻译成「两个前缀和相差 S」再用频率数组把统计复杂度从 O(n²) 降到 O(n)。仓库实现 仅 15 行核心代码便同时兼顾了正确性freq[0] 1的初始化、t 0的剪枝、性能O(n) 时间、定长数组与可读性关键步骤附有中文注释与调试输出配合 测试用例 中的全零边界用例构成了一个值得反复研读的「前缀和计数」标准范例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
