和为 K 的子数组

怎样从“nums 连续子数组和=k 个数。”推导出 前缀和 · 和为 K，并证明每次状态变化都不会漏掉答案？

中心结论：prefix map 存频次;ans+=map[prefix-k]。

给你一个整数数组 `nums` 和一个整数 `k` ，请你统计并返回该数组中和为 `k` ****的连续子数组的个数。

在本站主例中，nums 连续子数组和=k 个数。

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

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

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

1. 1建模把输入翻译成“前缀累计仪”，明确答案需要观察什么。
2. 2状态只维护 prefix sum、map 计数。
3. 3转移每一步按照 prefix map 存频次;ans+=map[prefix-k]。
4. 4收尾读取 子数组个数。，并复核边界与复杂度。

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

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

此题不能使用滑动窗口来解。因为 `nums[i]` 可能为负数。 前缀和的思路可以解答此题，但是时间复杂度有点高了，`O(n^2)`。考虑优化时间复杂度。 题目要求找到连续区间和为 `k` 的子区间总数，即区间 `[i,j]` 内的和为 K ⇒ `prefixSum[j] - prefixSum[i-1] == k`。所以 `prefixSum[j] == k - prefixSum[i-1]` 。这样转换以后，题目就转换成类似 A + B = K 的问题了。LeetCode 第一题的优化思路拿来用。用 map 存储累加过的结果。如此优化以后，时间复杂度 `O(n)`。

prefix map 存频次;ans+=map[prefix-k]。

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

正确性依赖以下不变量：map 记录前缀出现次数。

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

落到当前题，执行机制可以压缩为：prefix map 存频次;ans+=map[prefix-k]。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

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

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

func subarraySum(nums []int, k int) int {
	count, pre := 0, 0
	m := map[int]int{}
	m[0] = 1
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if _, ok := m[pre-k]; ok {
			count += m[pre-k]
		}
		m[pre] += 1
	}
	return count
}

func main() {
    // 1. 主例
    //    输入：mode="subarray-sum-k", nums=[1,1,1], k=2
    //    期望：子数组个数。
    //
    // 2. 失败 / 未命中
    //    检查：prefix-k 出现几次就有几个子数组。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC525 连续数组；LC974 整除
}

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

1. 1题意nums 连续子数组和=k 个数。
2. 2重复每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。
3. 3优化prefix map 存频次;ans+=map[prefix-k]。
4. 4证明map 记录前缀出现次数。
5. 5复杂度时间 O(n)，空间 O(1)