近期2026 年 8 月 21 日铜陵市教体局、科协印发了《关于举办 2026 年铜陵市青少年编程大赛的通知》比赛设 C 项目小学 / 初中 / 高中组是地市级算法赛的典型代表。这类比赛里有一类老熟人题型——对连续一段数据求和并找特征区间入门组几乎必考稍难一点的区赛、市赛也常把它当压轴小问。很多同学一看到连续子段就本能地写两层循环暴力枚举结果 n 一上 10⁵ 就超时。今天这篇文章用一道原创题把前缀和 哈希表这一招讲透把 O(n²) 的暴力直接压成 O(n)无论是最长和为 0 的子段还是和为 K 的子段个数都能一套通吃。一、题目科技节摊位人气波动【背景】学校科技节连续 n 天对一个摊位做人气打卡第 i 天的人气净变化为 a[i]可正可负正数代表新增关注负数代表流失。【问题 A · 基础】求人气净变化恰好为 0的最长连续天数区间长度即最长的、元素和为 0 的连续子数组长度。【问题 B · 进阶】给定目标整数 K求人气累计净增长恰好为 K的连续区间个数即元素和恰好等于 K 的连续子数组个数。【输入格式】n K a[1] a[2] ... a[n]【数据范围】1 ≤ n ≤ 2×10⁵−10⁹ ≤ a[i] ≤ 10⁹K 为 int 范围内整数。【样例】输入 8 2 3 -1 2 -2 1 -3 1 2 输出 7 4解释问题 A 最长和为 0 的区间是第 2~8 天[-1, 2, -2, 1, -3, 1, 2]长度 7问题 B 中和为 2 的子数组有 4 个[3,-1]、[2]、[3,-1,2,-2]、[2]。二、核心考点拆解前缀和Prefix Sum用s[i]表示前 i 个元素的和则任意子数组a[l..r]的和 s[r] - s[l-1]。把子段和转成了两个前缀和之差。哈希表记录首次出现位置问题 A 要和为 0等价于找两个前缀和相等s[r] s[l-1]区间长度 r - (l-1)为了让区间最长每个前缀和只记它第一次出现的位置。哈希表计数问题 B 要和为 K等价于找s[r] - s[l-1] K即之前出现过s[l-1] s[r] - K的次数用哈希表累加计数。边界空前缀下标 0 处有一个和为 0 的空前缀必须提前放入哈希表否则会漏掉从第 1 个元素就开始的区间。数值范围a[i] 可达 1e9前缀和需用long long/int64否则溢出。复杂度跃迁暴力枚举 O(n²) 在 n2×10⁵ 时必超时哈希法 O(n) 轻松过。三、解法一最长和为 0连续子段思路遍历前缀和若当前和s之前见过说明中间这段和为 0用当前下标 − 首次出现下标更新答案若没见过才记录位置只记首次不更新这样才能取到最长。#include iostream #include vector #include unordered_map using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int firstPos; // 某前缀和第一次出现的位置 firstPos[0] 0; // 空前缀下标 0 long long s 0; int ans 0; for (int i 1; i n; i) { s a[i - 1]; if (firstPos.count(s)) { ans max(ans, i - firstPos[s]); // 区间 [firstPos[s]1, i] 和为 0 } else { firstPos[s] i; // 只记录第一次保证区间最长 } } cout ans endl; return 0; }def longest_zero_sum(arr): first_pos {0: 0} # 空前缀下标 0 s 0 ans 0 for i, x in enumerate(arr, start1): s x if s in first_pos: ans max(ans, i - first_pos[s]) else: first_pos[s] i # 只记录第一次出现 return ans四、解法二进阶子段和恰好为 K 的个数思路边走边维护哈希计数cnt[前缀和]。每读入一个新元素先看之前有多少个前缀和等于s - K那就是以当前为右端、和为 K 的区间数累加后再把当前s计入哈希。注意顺序先查询、再加当前 s否则会把自己减自己误算进去。#include iostream #include vector #include unordered_map using namespace std; int main() { int n; long long K; cin n K; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; unordered_maplong long, int cnt; cnt[0] 1; // 空前缀 long long s 0; long long ans 0; for (int i 0; i n; i) { s a[i]; if (cnt.count(s - K)) ans cnt[s - K]; // 先查历史 cnt[s]; // 再记当前 } cout ans endl; return 0; }from collections import defaultdict def count_sum_k(arr, K): cnt defaultdict(int) cnt[0] 1 s 0 ans 0 for x in arr: s x ans cnt[s - K] # 先查历史 cnt[s] 1 # 再记当前 return ans五、时间 / 空间复杂度时间复杂度两个解法都只遍历数组一次每次哈希操作为均摊 O(1)整体O(n)。空间复杂度哈希表最多存 n1 个不同前缀和O(n)。相比暴力 O(n²) 既快又省。六、易错点清单忘记放空前缀cnt[0]1/firstPos[0]0不初始化会漏掉从第一个元素起就满足条件的区间。问题 A 误更新首次位置如果每次都写firstPos[s] i取到的是最近一次而非第一次区间变短、答案偏小。正确做法是见过就跳过没见过才记录。问题 B 顺序写反先cnt[s]再查s-K会把当前区间自己当成历史前缀多算。整数溢出a[i] 与 K 都很大时前缀和用 32 位 int 会溢出C 务必long longPython 无此忧。负数取模进阶坑若题目改成子段和能被 m 整除的个数存s % m时 C 负数取模为负需写成(s % m m) % m。数据规模意识n2×10⁵ 时任何 O(n²) 写法包括看似聪明的枚举起点都会 TLE认准 O(n) 哈希法。七、再进阶三个方向方向 1 · 同余前缀和求子段和能被 m 整除的区间个数 → 前缀和取模 哈希计数处理负数取模是蓝桥杯、电子学会考级里的常客。方向 2 · 二维前缀和矩阵中和恰为 K 的子矩形个数 → 固定上下边界把矩阵压成一维数组直接套本题思想。方向 3 · 哈希去重求不同子数组和的种类数 → 把所有前缀和的两两之差塞进集合去重思路一脉相承。方向 4 · 与滑动窗口对比当数组全为非负时求和不超过 K 的最长子段可用双指针滑动窗口一旦含负数滑动窗口失效必须回归前缀和 哈希。八、小结与互动前缀和 哈希表是少儿编程算法赛道里性价比最高的一招把连续子段求和从暴力 O(n²) 一把拉到 O(n)既能解最长和为 0也能解和为 K 的个数还能横向扩展到同余、二维、去重。建议把上面的样例在本地跑一遍、改改数据自己出几组真机手感比看十遍都牢。互动时间你在地市级 / 区县级编程赛里还遇到过哪些前缀和变形题或者哪一步最容易卡住欢迎在评论区留言下一篇我们可以挑二维前缀和或单调队列接着讲。原创算法题转载请注明出处。配套练习与讲解持续更新中。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。