企业官网建设流程全解析

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.md）：

In 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] = 1+0+1 [1,0,1,0,1] → A[1..3] = 0+1+0+1 [1,0,1,0,1] → A[2..4] = 1+0+1 [1,0,1,0,1] → A[0..4] = 1+0+1+0+1

题目大意

用一句话概括：给定一个只包含0和1的数组，问有多少个和为S的连续子数组。

数据范围与约束

原文档给出的约束条件如下：

• A.length <= 30000
• 0 <= S <= A.length
• A[i]的取值只能是0或1

约束中两个关键点直接影响解法设计：

1. 数组长度可达 30000：O(n²) 的暴力枚举（枚举所有[i, j]区间并求和）在最坏情况下需要约 9 亿次操作，不可接受，必须设计 O(n) 或 O(n log n) 的算法；
2. 元素非 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[j+1] - prefix[i]

题目要求sum(A[i..j]) == S，即：

prefix[j+1] - prefix[i] == S ⇔ prefix[i] == prefix[j+1] - S

于是问题转化为：遍历到当前位置j时，历史上出现过多少个前缀和等于prefix[j+1] - S？每出现一个，就对应一个以j结尾的合法子数组。这正是「前缀和 + 哈希计数」解法的本质。

频率数组 freq 的含义

原文档对freq的说明：

在 freq 中不断的记下能使得和为 sum 的组合方法数，例如 freq[1] = 2，代表和为 1 有两种组合方法，（可能是 1 和 1，0 或者 0，1，这道题只管组合总数，没要求输出具体的组合对）。

即：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 }

逐行拆解：

这里有一个细节值得注意：t >= 0的判断。因为数组元素非负，前缀和单调不减，所以对任意历史位置i，都有prefix[i] <= prefix[j+1]，即prefix[i] - (prefix[j+1] - S) = S >= 0恒成立；反过来，若t < 0，则意味着目标前缀和小于 0，而前缀和永远非负，必然没有历史命中。因此t >= 0是一个合法的剪枝判断，也是数组索引安全的保证（避免freq越界访问负下标）。

同时可以看到：t的计算发生在sum更新之前，用的是「加入v之后的前缀和」去减S，这与等式prefix[j+1] - prefix[i] = S完全对应。

手工推演：以仓库测试用例为例

推演示例一：A = [1,0,1,0,1]，S = 2

仓库测试用例给出的期望答案是4。我们逐步推演：

最终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。用算法推演：

每一步的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与目标值k），ans930描述期望输出，三个用例分别是：

第二个用例（全零数组 + S=0）是最有价值的边界测试：它同时检验了「空子数组是否被误计」（结果 15 恰好是非空子数组总数n(n+1)/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数组长度为n+1，用于存储各个前缀和的出现次数。若将freq换为哈希表，空间复杂度在平均情况下可视为 O(n) 但常数更大；由于前缀和值域已知且连续，定长数组是更优选择，也避免了哈希冲突。

延伸思考：相关解法与题目家族

滑动窗口视角与本题的特殊性

原文档将本题归为「滑动窗口的题目」，这里补充说明为什么典型的双指针滑动窗口需要额外处理：经典的双指针滑动窗口（如 76. Minimum Window Substring）适用于「窗口和满足单调性」的场景，但本题数组包含 0，S = 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