和相同的二元子数组

怎样从“nums 全 0/1,子数组和=goal 个数。”推导出 前缀和 · 二元子数组，并证明每次状态变化都不会漏掉答案？

中心结论：同 LC560:prefix 计数 map,加 map[prefix-goal]。

给定一个数组，数组里面的元素只有 0 和 1 两种。问这个数组有多少个和为 S 的子数组。

在本站主例中，nums 全 0/1,子数组和=goal 个数。

算法最终需要得到或观察：和为 goal 的子数组个数。

每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“前缀累计仪”，明确答案需要观察什么。
2. 2状态只维护 prefix、map。
3. 3转移每一步按照 同 LC560:prefix 计数 map,加 map[prefix-goal]。
4. 4收尾读取 和为 goal 的子数组个数。，并复核边界与复杂度。

把“某段区间”改写成“两个前缀之间的关系”。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：prefix、map。

这道题也是滑动窗口的题目。不断的加入右边的值，直到总和等于 S。[i,j] 区间内的和可以等于 [0,j] 的和减去 [0,i-1] 的和。在 freq 中不断的记下能使得和为 sum 的组合方法数，例如 freq[1] = 2 ，代表和为 1 有两种组合方法，(可能是 1 和 1，0 或者 0，1，这道题只管组合总数，没要求输出具体的组合对)。这道题的做法就是不断的累加，如果遇到比 S 多的情况，多出来的值就在 freq 中查表，看多出来的值可能是由几种情况构成的。一旦和与 S 相等以后，之后比 S 多出来的情况会越来越多(因为在不断累积，总和只会越来越大)，不断的查 freq 表就可以了。

同 LC560:prefix 计数 map,加 map[prefix-goal]。

执行过程中持续维护：prefix、map。

正确性依赖以下不变量：0/1 数组 prefix 递增? 0/1 仍可计数。

面试时可以压缩为：前缀和+map O(n)。

落到当前题，执行机制可以压缩为：同 LC560:prefix 计数 map,加 map[prefix-goal]。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums 全 0/1,子数组和=goal 个数。 因为：同 LC560:prefix 计数 map,加 map[prefix-goal]。
2. 2prefix=1,查 -1 出现 0 次累加前缀,查补前缀。 因为：O(n) 哈希计数。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4count[1] 更新前缀入库。 因为：供后续 j 查询。
5. 5count[2] 更新前缀入库。 因为：供后续 j 查询。
6. 6count[2] 更新前缀入库。 因为：供后续 j 查询。
7. 7count[3] 更新前缀入库。 因为：供后续 j 查询。
8. 8收尾与复杂度和为 goal 的子数组个数。 因为：时间 O(n) · 空间 O(1)。同 LC560:prefix 计数 map,加 map[prefix-goal]。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "fmt"

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
}

func main() {
    // 1. 主例
    //    输入：mode="subarray-sum-k", nums=[1,0,1,0,1], k=2
    //    期望：和为 goal 的子数组个数。
    //
    // 2. 失败 / 未命中
    //    检查：与 560 同模板。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC560；LC974
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums 全 0/1,子数组和=goal 个数。
2. 2重复每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。
3. 3优化同 LC560:prefix 计数 map,加 map[prefix-goal]。
4. 4证明0/1 数组 prefix 递增? 0/1 仍可计数。
5. 5复杂度时间 O(n)，空间 O(1)