统计目标和子数组
结合前缀和与哈希表
统计目标和子数组 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
更难的问题
现在来看一个变化：计算和为目标值 k 的子数组数量。检查每一对端点会很慢，但前缀和加上哈希映射就能解决它。🎯
用前缀和重新思考
子数组的和等于 prefix[r + 1] 减去 prefix[l]。因此，和为 k 就意味着两个前缀值恰好相差 k。
关键变形
如果当前前缀和是 P，您就需要一个早先出现过的、等于 P 减 k 的前缀和。这个变形就是整个技巧的核心。
need = current_prefix - k计数，而不是查找
不要每次都向前扫描，而应记住每个前缀值出现过多少次。持续维护的计数可以在 O(1) 时间内给出答案。
使用频率映射
字典将每个前缀值映射到它出现的次数。这个映射将查找变成了即时计数。
from collections import defaultdict
seen = defaultdict(int)初始化空前缀
在循环开始前，请记录前缀和 0 已经出现过一次。这个初始记录可以让从索引 0 开始的子数组被正确计数。
seen[0] = 1单次遍历循环
对于每个元素，请更新当前前缀和，加上所需值的出现次数，然后记录当前前缀和。一次遍历就能完成全部工作。
total += x
count += seen[total - k]
seen[total] += 1顺序为何重要
您必须先将次数加到答案中，再记录当前前缀和。否则会混入长度为零的范围，导致计数出错。
速度优势
每个元素只需进行常数次操作，因此整个计数过程的复杂度是 O(n)。在较大的输入上，这优于 O(n²) 的暴力方法。
负数也适用
与滑动窗口不同，这种方法可以很好地处理负数，因为无论符号如何，前缀和之差都保持有效。
经典应用场景
这个模式可以解决著名的“子数组和等于 k”问题，以及竞赛评测中许多伪装后的变体。
快速检查
您的当前前缀和是 P，目标值是 k。
总结
您可以使用前缀和和频率映射，在 O(n) 时间内计算目标和子数组的数量。先初始化前缀和 0，再计数，最后记录当前前缀和。✅
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「统计目标和子数组」课时是免费的吗？
是的 — 「统计目标和子数组」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「统计目标和子数组」这节课中我会学到什么？
结合前缀和与哈希表 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「统计目标和子数组」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 构建前缀和数组
- 使用减法求任意区间和
- 统计目标和子数组
- 用于区间更新的差分数组