如果你也在牛客网上刷题看到NC16589这个编号应该不陌生。我最近重新刷到它时突然想把这题好好复盘一下因为第一次做的时候我就栽了跟头老老实实写了三层循环样例过了提交直接超时整个人都不太好。后来冷静下来才发现这题考的就是前缀和加哈希表属于看着简单、实则很考验基本功的那种题。先把题意给大家说清楚方便没刷过这题的朋友也能跟上思路给定一个长度为 n 的整数数组 a再给一个目标值 k统计有多少个非空连续子数组它们的和恰好等于 k。这里的 n 最大可以到 10^5 级别数组元素可以是正数、负数也可以是 0。你不需要做任何修改操作只需要计数。适合谁看准备机试、笔试、面试手写代码的同学以及所有想把前缀和优化思路彻底搞明白的初学者。这篇文章不会只贴一个最终代码而是把我从暴力到 AC 的完整过程、踩过的坑和排查方法都写出来有些细节常规题解里根本不会提。1. 拿到题目别急着写代码先做三件事1.1 把题面翻译成一句人话很多同学刷题第一反应是打开编辑器对着样例就开始写。我之前也这样结果经常是写完才发现把题意理解偏了。现在我拿到任何一道题第一件事都是把题面压缩成一句人话。对NC16589来说这句话就是统计区间和等于 k 的区间数量。只有把“连续子数组”翻译成“区间”才能想起那一整套区间求和工具前缀和、差分、滑动窗口、树状数组、线段树。因为题目只要求计数不要求修改树状数组和线段树基本可以排除。又因为数组里有负数滑动窗口的双指针也不是优先选择。于是在写第一行代码之前我已经把方向缩小到了前缀和这条路上。这种“翻译题面”的习惯非常有用。很多题的难点不在算法本身而在于你根本没有意识到它本质上是个区间问题。把“连续子数组”“子串”“子段”这些词都统一成“区间”你的武器库瞬间就被激活了。1.2 数据范围决定算法而不是手感决定算法n 最大能到 10^5如果枚举左右端点O(n^2) 大概是 10^10 次运算。在评测机上跑完需要几十秒这显然不是出题人的本意。相比之下O(n log n) 甚至 O(n) 才是这个数据规模下该有的复杂度。我第一版的做法是先算好前缀和再用两层循环枚举 i 和 j判断 pre[j] - pre[i] 是否等于 k。样例自然能过提交后却显示 TLE。后来仔细看数据范围才发现n 是 10^5 级别O(n^2) 必挂。这件事教会我一件事做题前先看 n不要先看样例。数据范围会直接告诉你暴力能不能走通也能告诉你要不要费力气优化。举个例子如果 n 只有 100那 O(n^3) 都可能秒过根本不用花心思写哈希表。可一旦 n 来到 10^5你心里就得有一张复杂度对照表O(n^2) 大概要几秒O(n log n) 大约能接受O(n) 才是稳妥解。这张表不需要背刷多了自然就有感觉。1.3 为什么我仍然建议先在草稿纸上写暴力虽然最终解法是 O(n)但我还是会在草稿纸上先写出暴力版本。暴力版本最大的价值不是跑分而是确认自己对题意的理解没有偏差。尤其是“非空”和“连续”这两个词很容易被忽略。如果你连暴力都写不对那你优化的方向再对也没有用。我的习惯是先写三重循环版本确认结果正确再优化成前缀和两重循环最后一步再跳到哈希表。每一步都用同一组小数据验证。这样万一最终答案错了我能很快定位到是哪一步出的问题。直接照抄最优解看起来很爽但出了问题你根本不知道错在哪这是刷题的大忌。2. 从 O(n^3) 到 O(n)三个版本的重构过程2.1 第一个版本三重循环求稳但不可用最原始的写法是枚举区间起点 i、终点 j再枚举区间内的元素 t 累加和。这段代码的正确性一目了然但复杂度是 O(n^3)稍大一点的数据就扛不住。int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { int sum 0; for (int t i; t j; t) { sum a[t]; } if (sum k) ans; } }这段代码的唯一作用就是帮我们锁定计数逻辑i 可以从 0 到 n-1j 可以从 i 到 n-1i 等于 j 时表示单个元素也算一个子数组。如果你用这段代码跑小数据能得到正确答案说明你对题意的理解是对的。接下来才轮到性能优化。我当时写这个版本的时候还犯过一个低级错误把 i 从 1 开始枚举j 也从 1 开始结果把第一个元素漏掉了。这种错误在最原始版本里很容易发现但如果直接写优化版本你可能会怀疑是哈希表的逻辑问题最后查半天发现是下标越界非常浪费时间。2.2 第二个版本前缀和把区间求和变成 O(1)前缀和数组 pre 的定义是 pre[i] a[0] a[1] ... a[i-1]那么区间 [i, j) 的和就是 pre[j] - pre[i]。有了前缀和就不再需要第三层循环了两层枚举即可。vectorint pre(n 1, 0); for (int i 0; i n; i) pre[i 1] pre[i] a[i]; int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (pre[j] - pre[i] k) ans; } }这里有个特别容易错的下标问题pre 的长度是 n1pre[0] 表示空前缀pre[1] 表示包含 a[0] 的前缀以此类推。区间 [i, j) 对应的是 pre[j] - pre[i]。如果你习惯让 pre[i] 表示前 i 个元素的和那么枚举时 j 一定要从 i1 到 n不能从 i 到 n-1否则会把非法区间也算进去。这个版本已经能应付 n 1000 的数据了但对 10^5 还是无能为力。它的意义在于让你直观感受到前缀和把区间和的计算成本降到了 O(1)接下来只差最后一层枚举没有优化掉。2.3 第三个版本哈希表把枚举砍成一遍扫描优化的核心灵感来自移项。我们要统计有多少对 (i, j) 满足 pre[j] - pre[i] k移项之后就是 pre[i] pre[j] - k。也就是说当我们扫描到某个前缀和 pre[j] 时只需要知道在它之前已经出现过多少个值为 pre[j] - k 的前缀和。这个“出现过多少次”的需求正好是哈希表最擅长的事。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int cnt; cnt[0] 1; // 空前缀表示 pre[0] 0 long long pre 0; long long ans 0; for (int i 0; i n; i) { pre a[i]; auto it cnt.find(pre - k); if (it ! cnt.end()) ans it-second; cnt[pre]; } cout ans \n; return 0; }cnt[0] 1 为什么必不可少因为区间 [0, j) 的和等于 k 时等价于 pre[j] - pre[0] k而 pre[0] 0 是空前缀。如果不提前把它放进去所有从下标 0 开始的合法区间都会被漏掉。这一步在最终代码里看似不起眼却是最容易丢分的点。复杂度方面每个前缀和只会被查询一次、插入一次哈希表平均复杂度 O(1)所以整体是 O(n)空间 O(n)。在 n 10^5 时运行时间几乎可以忽略不计。3. 核心细节与原理拆解为什么这样做是对的3.1 前缀和的本质是“区间变成两点之差”前缀和不复杂但很多人只是背了模板不理解它为什么能和哈希表配合。其实前缀和把区间求和问题变成了两点之差问题任意子数组和都能写成两个前缀和的差。我们要统计有多少对差值为 k 的前缀和固定当前这个前缀和 pre问题就变成“之前出现过多少个 pre - k”。这是一次典型的空间换时间也是哈希表能发挥作用的最大原因。用一个生活化的类比来解释前缀和就像是记账。你记录每天累计花了多少钱想知道某几天一共花了多少钱只需要把两天的累计数相减不需要天天数。这道题更进一步不光想知道某一笔花了多少钱还想知道一共有多少对日期的累计差额正好等于 k。哈希表就是那个帮你在账本里快速查“某个累计数出现过几次”的工具。这个思想可以泛化。凡是“统计满足某种关系的区间数量”的题第一步都是把区间关系转化成两个前缀之间的关系。后面我会提到“和能被 k 整除”的变体它用的也是同一个套路只是把“差值等于 k”换成“差值模 k 等于 0”。3.2 有负数时滑窗就失效了看到“连续子数组”很多人第一反应是双指针滑动窗口。但滑动窗口成立的前提是窗口和随着右指针右移单调变化。在一堆正数里右指针右移窗口和只会变大所以收缩左边界有明确依据。可数组一旦出现负数窗口和就可能忽大忽小你根本不知道右指针走后窗口和会怎么变滑动窗口的正确性就没了。NC16589 的数据里明确包含负数和 0这是很多人的第一个坑。如果题目没有负数其实用滑动窗口写起来更短每个元素进出一遍O(n) 也能过。但这题不行所以必须回到前缀和加哈希表。我在讨论区看到有人用 unordered_map 还是 TLE点进去一看他其实是在两重循环里用 unordered_map 查东西复杂度根本没降下来这是实现思路的问题不是哈希表的锅。判断“能不能用滑动窗口”有个很简单的标准数组里有没有负数或者窗口和随右指针移动是否单调。只要不单调窗口收缩就没有依据滑窗直接出局。遇到这种题脑子里就要自动切换到前缀和。3.3 三个实现细节任何一个都可能让你 WA第一数据类型一定要用 long long。n 最大 10^5a_i 的绝对值又能到 10^9 级别前缀和累加很容易超过 int 的范围。我一开始写了 int pre样例一切正常提交就 WA排查了好久才发现是溢出。这种问题最恶心的地方在于不会报错只会给你一个看似莫名其妙的结果。所以写这种和“和”相关的题目我现在的习惯是直接 long long省得后面还要回去改。第二unordered_map 和 map 怎么选。map 的查询是 O(logn)在 n10^5 时其实也能过但完全没有必要。unordered_map 平均 O(1)用起来更舒服。如果你担心极端数据让 unordered_map 退化可以手写哈希或者用数组模拟但刷题阶段按默认来就好。还有一种更稳的做法是提前 reserve 容量减少扩容带来的常数开销追求性能时可以写上。第三先查后插的顺序死都不能忘。必须先在哈希表里查询 pre - k再把当前 pre 插入。如果顺序反了当前这个前缀和会被当成“之前出现过的前缀和”导致区间长度为 0 的情况也被计入答案。构造一个 k0 的全 0 数组你就会发现答案瞬间多出一大截。这个错误很难通过小样例发现因为一般小样例里恰好没有这种巧合但它就是会在关键时刻给你一刀。4. 实战排查与常见问题速查4.1 我用这几组用例验证正确性下面是当时用来自测的测试数据建议你写完后也照着跑一遍输入k期望输出考察点[1,1,1]22普通正数计数[1,-1,0]03负数、0 混在一起[0,0,0]06单个元素和长度为2、3的区间全是0[1]11单元素边界[1,2,3]70无解情况[-1,-1,-1]-13目标值是负数也能查全 0 数组是我印象最深的一个用例。数组长度 3 的非空连续子数组共有 6 个每个的和都是 0所以答案必须是 6。如果你漏写 cnt[0] 1或先插后查这一组用例会直接让你的答案变成 3 或者 9逻辑问题立刻现形。4.2 当 WA 的时候我一般这样查遇到 WA我很少盯着代码发呆而是会拿一个长度不超过 5 的数组在纸上把每一步 pre 的值写出来再对照哈希表模拟一次查询和插入。比如数组 [1, -1, 0]k0正确结果应该是 3。你可以手动过一遍初始 cnt[0] 1pre 0处理 a[0] 1pre 1查 cnt[1] 没有插入 cnt[1] 1处理 a[1] -1pre 0查 cnt[0] 有 1 个ans 1插入 cnt[0] 变为 2处理 a[2] 0pre 0查 cnt[0] 有 2 个ans 3插入 cnt[0] 变为 3这里第二次和第三次查到的 cnt[0]分别对应不同的前缀和位置。用前缀和数组的眼光看cnt[0] 一开始是 S[0]第二次是 S[2] 加入第三次则是 S[0] 和 S[2] 同时存在于哈希表里。这些值对应着不同起点的合法区间所以能够安全累加。配合打印语句把每一步的 pre 和查询结果输出比对答案就很容易定位是插入时机错了、取模错了还是漏了 cnt[0]。我调试时还喜欢把答案输出类型改成 long long避免看着被截断的数字怀疑人生。另一个小技巧是如果 WA 来自边界优先检查空数组、只有一个元素、全正数、全负数这四种极端输入。绝大多数边界 bug 都能在这四种输入里暴露。4.3 顺手记住几个变体面试时能直接用NC16589 的思路可以迁移到很多相似题目。面试时如果遇到“和为 k 的子数组数量”直接套哈希表前缀和是标准答案。如果题目变成“和为 k 的倍数的子数组数量”只需要把前缀和改成对 k 取模后的值再入哈希表注意负数的取模要和语言行为一致C 里 -1 % 5 是 -1你可能需要先加 k 再取模否则统计会乱套。还有一个常见变体是“和等于 k 的最短连续子数组长度”。同样可以用前缀和加哈希表哈希表里存的是某个前缀和最早出现的位置扫描时遇到 pre - k就用当前位置和存储位置做差更新答案。这类问题本质都是把区间问题转化成两个前缀和的关系这就是一次性掌握一类题的价值。4.4 先判断是全 WA 还是只错边界还有一个小经验拿到一个报错的提交先别急着改代码看看是一组数据都没过还是只挂在某些大用例上。全 WA 一般是思路问题比如你错用了滑动窗口或者哈希表维护的东西不对只有大用例出错往往是类型溢出或者插入顺序的问题只有边界用例出错八成就是 cnt[0] 漏了或者下标处理错了。这种分类排查方法能帮你节省大量时间。我第一次做这道题的时候被 TLE 折磨了很久一直以为是常数问题反复优化 IO。后来把复杂度重新一算才发现两层循环就是两层循环再怎么优化 IO 都救不回来。所以遇到非预期超时第一反应应该是看复杂度而不是抠常数。5. 这道题还能怎么延伸5.1 扩展到二维矩阵子矩阵和为 k如果把一维数组换成二维矩阵问题就变成统计有多少个子矩阵的和等于 k。直接枚举四个边界是 O(n^4)显然不现实。常见的做法是枚举行上下边界然后对每一列做前缀和压缩成一维数组再利用 NC16589 的哈希表方法统计。这样能把复杂度降到 O(n^3)在 n 较小的时候是可行的。这个扩展特别能检验一个人的基本功。如果你能把一维解法原封不动塞进二维的循环里说明你真正理解了前缀和加哈希表的本质。很多面试官也喜欢这样一层层加难度从一维数组问到二维子矩阵再问到带负数的情况都是同一个套路的变化。5.2 从“数量”变成“方案数”有时候题目要求的不只是区间数量而是最大长度、最小长度甚至区间本身。这时候哈希表里存的值就要改一改。比如求最大长度哈希表里存某个前缀和最早出现的位置求最小长度同样存最早位置只是更新答案的方向反了。核心的“查 pre - k”逻辑不会变变的只是你在命中之后如何处理答案。这种“同一框架下换需求”的训练很有价值。刷题不能只背代码要背的是那套“移项 哈希表”的思考流程。遇到任何区间和问题先写出区间和的表达式再尝试移项最后看看能不能用一个哈希表维护已经出现的前缀信息。这一步想通了题目再怎么变你都有方向。5.3 如果 k 的范围非常大呢还有一种情况是 k 的范围很大但 n 很小。这时候依然可以用哈希表不需要额外处理。复杂度只和 n 相关和 k 的大小没有关系。反之如果 a_i 的范围很小甚至可以用数组代替哈希表这就是用空间换时间的一种体现。我在牛客的讨论区里见过有人问“为什么不用二分找边界”答案其实很简单数组元素可正可负前缀和不单调二分不能在无序数组上工作。如果你先对前缀和排序又会丢失位置关系反而更麻烦。所以哈希表几乎是这个场景下的最优解。最后几句最后说一点我自己刷题的心得NC16589 这类题真正难的不是哈希表而是你能不能在写代码前判断出“不能用滑动窗口”和“需要 cnt[0]1”。我踩过几次坑之后养成了个习惯——任何涉及连续子数组的题先看一眼数组有没有负数有负数就第一时间关掉滑窗思路再确认 n 的数据范围把 O(n^2) 的幻想直接掐掉。这两个条件一确定解法基本就锁死了。再多说一个小技巧如果你的哈希表用的是 unordered_map建议在赛前把 cin 和 cout 的同步关掉也就是写上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。这道题数据量大时这两行代码能让你的程序快得非常明显。刷题不是比谁代码写得快而是比谁在动键盘之前更清楚自己在做什么。希望这篇复盘能让你下次遇到区间和计数问题时少走几步弯路。