近期（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]。
二、核心考点拆解
三、解法一：最长"和为 0"连续子段
思路：遍历前缀和，若当前和 s 之前见过，说明中间这段和为 0，用"当前下标 − 首次出现下标"更新答案；若没见过才记录位置（只记首次，不更新，这样才能取到最长）。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
unordered_map<long 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, start=1):
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;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
unordered_map<long 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)。
- 空间复杂度：哈希表最多存 n+1 个不同前缀和，O(n)。相比暴力 O(n²) 既快又省。
六、易错点清单
七、再进阶：三个方向
- 方向 1 · 同余前缀和：求"子段和能被 m 整除"的区间个数 → 前缀和取模 + 哈希计数（处理负数取模），是蓝桥杯、电子学会考级里的常客。
- 方向 2 · 二维前缀和：矩阵中"和恰为 K 的子矩形"个数 → 固定上下边界把矩阵压成一维数组，直接套本题思想。
- 方向 3 · 哈希去重：求"不同子数组和的种类数" → 把所有前缀和的两两之差塞进集合去重，思路一脉相承。
- 方向 4 · 与滑动窗口对比：当数组全为非负时，求"和不超过 K 的最长子段"可用双指针滑动窗口；一旦含负数，滑动窗口失效，必须回归前缀和 + 哈希。
八、小结与互动
前缀和 + 哈希表是少儿编程算法赛道里性价比最高的一招：把"连续子段求和"从暴力 O(n²) 一把拉到 O(n)，既能解"最长和为 0"，也能解"和为 K 的个数"，还能横向扩展到同余、二维、去重。建议把上面的样例在本地跑一遍、改改数据自己出几组，真机手感比看十遍都牢。
互动时间：你在地市级 / 区县级编程赛里还遇到过哪些"前缀和"变形题？或者哪一步最容易卡住？欢迎在评论区留言，下一篇我们可以挑"二维前缀和"或"单调队列"接着讲。
原创算法题，转载请注明出处。配套练习与讲解持续更新中。
📚 免费少儿编程资料（夸克网盘领取）
以下资料来自夸克网盘分享，点击链接可直接保存；若需在 App 内打开，也可复制下方明文链接：
资料持续更新，关注获取最新分享。
