优化到O(n))
GESP 2024年9月的三级认证里，第三部分编程题第一题叫"平衡序列"。这道题和前面几道模拟题画风不太一样，它更像一道纯粹的算法题——如果你只会老老实实把每个区间都试一遍，大概率只能过掉前几个小数据点，后面全超时。我当时第一次写的就是暴力O(n²)，交上去TLE之后才去琢磨怎么用前缀和加哈希把它压成O(n)。这篇文章把整个推导过程、完整C++代码和测试边界都整理出来，给接下来考GESP三级，或者正在学前缀和的同学做个参考。
1. 先还原题面：这道"平衡序列"到底在问什么
1.1 题目描述与输入输出约定
根据2024年9月GESP三级真题的常见回忆版本，题面大意如下：
给定一个长度为n的正整数序列a₁, a₂, …, aₙ。如果一段连续子序列a_l, …, a_r满足：该子序列中下标为奇数的数字之和等于下标为偶数的数字之和，则称这段子序列为平衡序列。求整个序列中最长平衡序列的长度，如果不存在，输出0。
输入格式：第一行一个整数n，第二行n个正整数。
输出格式：一个整数，表示最长平衡序列的长度。
比如输入：
8 1 2 3 4 4 3 2 1整个序列的奇数位下标1、3、5、7上的数字是1、3、4、2，和为10；偶数位下标2、4、6、8上的数字是2、4、3、1，和也是10，奇偶和相等，所以整个序列本身就是平衡的，输出8。
这道题有些同学会纠结"子序列中下标为奇数"到底指原序列下标还是子序列内部重新编号。对连续区间来说，这两种理解最终得到的判断条件是一样的，这个我在后面第三章会专门解释，现在先按住不表。
1.2 考点拆解：它考的不只是模拟
这道题的典型特征就是：题面读起来很简单，判断逻辑一句话能说清，但数据范围一大，模拟写法就没戏。GESP三级的编程题每年难度都在缓慢爬升，这道题其实已经摸到了四级前半段的门槛。
我列了一个考点对照表，方便你对照自己的薄弱环节：
| 考点 | 考察方式 | 说明 |
|---|---|---|
| 前缀和 | 把"区间和"转化为"两个前缀和的差" | 整个题的核心，前缀和也是后续四、五级反复出现的基础工具 |
| 查找表/哈希 | 用unordered_map或map记录状态首次出现的位置 | 把O(n²)降到O(n)的关键一步 |
| 数学等价变形 | 把"奇数和等于偶数和"变成"加权和为0" | 需要想到给偶数位加上负号 |
| 边界处理 | 空区间、无解、数据范围、下标起始位置 | 往往决定代码能不能一遍AC |
如果你已经把C++的数组、循环、函数这些基础掌握得比较熟了，这道题非常适合拿来练"从暴力到优化"的完整思考过程。
2. 暴力思路为什么会超时：从三重循环说起
2.1 最直观的枚举写法
刚拿到这道题，绝大多数人的第一反应就是枚举。枚举所有可能的左端点l和右端点r，然后遍历这个区间，分别累加奇数位和偶数位，判断是否相等。
long long ans = 0; for (int l = 1; l <= n; ++l) { for (int r = l; r <= n; ++r) { long long oddSum = 0, evenSum = 0; for (int k = l; k <= r; ++k) { if (k % 2 == 1) oddSum += a[k]; else evenSum += a[k]; } if (oddSum == evenSum) { ans = max(ans, (long long)(r - l + 1)); } } }这个写法复杂度是O(n³)，n到1000就已经是10亿次级别操作，评测机根本扛不住。GESP三级的数据范围通常会给到10⁵，所以这种写法只能说是"思路正确、得分可怜"。
2.2 两次优化后的O(n²)写法及其缺口
稍微聪明一点的同学会想到，固定左端点l之后，右端点r向右移动时，并不需要重新遍历整个区间，只要根据r的奇偶性，把a[r]加到对应的oddSum或evenSum里就行。
long long ans = 0; for (int l = 1; l <= n; ++l) { long long oddSum = 0, evenSum = 0; for (int r = l; r <= n; ++r) { if (r % 2 == 1) oddSum += a[r]; else evenSum += a[r]; if (oddSum == evenSum) { ans = max(ans, (long long)(r - l + 1)); } } }这个双循环版本是O(n²)。看着已经很不错了，但把n = 10⁵代进去，要做大约5×10⁹次加法，按评测机每秒10⁸次运算来估算，也要50秒往上。GESP考试单题时限一般就是1秒左右，所以这个复杂度在大数据点上依旧超时。
我第一次做这道题时就在这里卡了很久。明明枚举思路完全正确，代码也没写错，就是过不了。后来才意识到，这类题的正确思考方向不是"怎么把区间枚举得更高效"，而是"能不能不枚举区间，直接通过某个全局状态找到答案"。
3. 核心转化：把"奇偶和相等"变成"前缀和相等"
3.1 一个加权前缀和的定义
前缀和大家都熟，通常的定义是s[i] = s[i-1] + a[i]，表示前i个数的和。这题的关键在于，我们关心的不是普通总和，而是"奇数位总和减去偶数位总和"。
我定义一个加权前缀和：
s[i] = s[i-1] + (i是奇数 ? a[i] : -a[i])换句话说，遍历到奇数位置就加a[i]，遍历到偶数位置就减a[i]。s[0] = 0。
拿上面的例子算一下，a = [1, 2, 3, 4, 4, 3, 2, 1]，s数组依次是：
s0 = 0 s1 = 1 s2 = -1 s3 = 2 s4 = -2 s5 = 2 s6 = -1 s7 = 1 s8 = 0这个s数组看起来平平无奇，但里面藏着答案。
3.2 为什么前缀和相等就等价于区间平衡
对于任意区间[l+1, r]，s[r] - s[l]等于什么？
从l+1到r，凡是奇数位置贡献+a[i]，偶数位置贡献-a[i]，所以：
s[r] - s[l] = (区间内奇数位数字之和) - (区间内偶数位数字之和)如果s[r] == s[l]，那这两个和就相等，区间[l+1, r]就是平衡区间。
这里要注意下标错位：s[r]和s[l]相等，对应的是开区间(l, r]或者说[l+1, r]这个闭区间。比如上面的s8 = 0，s0 = 0，那么区间[1, 8]就是平衡区间，长度8。
之前我说"子序列内部重新编号"的理解方式结论也一样，原因很简单：一个连续区间里，奇数位置的下标集合和偶数位置的下标集合是固定的，只是如果左端点是偶数，区间内部的"奇数位"对应的是原数组的偶数位集合，但平衡条件比较的仍然是"原数组奇数位和 vs 原数组偶数位和"，两个集合没有变，只是把名字交换了一下。所以不管你怎么理解题面，判断标准都可以统一成加权前缀和是否为0。
3.3 最长区间的查找：哈希表记录首次出现位置
现在问题变成了：s数组里，哪两个位置的值相同，并且距离最远？
最直接的办法是遍历每个i，往前找有没有j < i满足s[j] == s[i]，取最大的i - j。但这样又是O(n²)。
优化思路是：用哈希表记录每个前缀和值第一次出现的位置。为什么要记"第一次"而不是"最后一次"？因为区间长度是i - first，first越小，i - first越大。所以记录最早出现的位置，能保证后面每次遇到相同值时，计算出来的都是最优长度。
遍历到位置i时：
- 如果s[i]之前出现过，最早出现位置是pos，那么区间[pos+1, i]是平衡区间，长度为i - pos，更新答案。
- 如果s[i]第一次出现，把它和位置i存进哈希表。
这样一遍扫描下来，每个位置只处理一次，总复杂度O(n)。
还是用上面的例子：i=8时，s8=0，而s0=0最早出现在位置0，所以区间[1,8]平衡，长度8。完美命中。
4. 完整C++实现：核心代码与那几个写错就白写的细节
4.1 可提交的完整代码
下面是完整可提交的C++代码，编译标准用C++11及以上就行。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } unordered_map<long long, int> first; first[0] = 0; long long cur = 0; int ans = 0; for (int i = 1; i <= n; ++i) { if (i & 1) { cur += a[i]; } else { cur -= a[i]; } auto it = first.find(cur); if (it != first.end()) { ans = max(ans, i - it->second); } else { first[cur] = i; } } cout << ans << '\n'; return 0; }核心逻辑只有十几行。如果你担心评测环境对unordered_map支持不友好，换成map也是一样的逻辑，复杂度变成O(n log n)，对n = 10⁵来说完全够用。
4.2 几个读起来不起眼但影响得分的实现细节
第一，关于"边读边算"还是"先存数组"。上面的代码先读入a，再统一扫描。其实也可以读入的时候就同步维护cur并判断，连vector都不用开。但我觉得先存数组更清晰，特别是调试的时候方便打印。
第二，为什么要用unordered_map<long long, int>而不是unordered_map<int, int>。n最多10⁵，a[i]最大可能到10⁹，加权前缀和的范围至少要到±10¹⁴，int根本装不下。用long long做key既安全又省心。
第三，两条对拍测试时最常见的隐蔽错误：
- 忘记初始化first[0] = 0。没有它，s[i] == 0这个最常见的情况就永远匹配不上。
- 用first[cur] == 0来判断是否存在，这个我会在第六章详细说，总之用find最稳妥。
第四，答案初始值是0。如果整个序列不存在任何平衡区间，输出0是完全合法的，不要因为样例输出都是正整数就怀疑自己。
5. 用样例和边界情况验证解法的正确性
5.1 多组样例推演
只跑通一个样例不算数，我把几组有代表性的输入都推演了一遍，整理成表格：
| 输入 | 输出 | 推演过程 |
|---|---|---|
| 8 1 2 3 4 4 3 2 1 | 8 | s8=0且s0=0，整个序列平衡 |
| 4 3 1 2 4 | 4 | s4=0，整个序列奇数位3+2=5，偶数位1+4=5 |
| 5 2 4 6 8 10 | 0 | 前缀和2,-2,4,-4,6，没有重复值 |
| 1 7 | 0 | 单个数字不可能让奇数位和等于偶数位和 |
| 4 2 2 2 2 | 4 | 奇数位2+2=4，偶数位2+2=4，整个序列平衡 |
| 3 2 2 2 | 2 | 整个序列奇数位4、偶数位2不平衡；但区间[1,2]奇数位2、偶数位2平衡，长度2 |
其中n=3全相等这个用例很值得关注。很多人会直觉认为"既然有两个2，那答案就是2"，但如果你没写对，可能输出3。这是检验代码对区间边界理解的好用例。
5.2 边界情况与数据范围
边界情况主要是这四类：
- n=1时，一定输出0，因为一个数没法让奇数和偶数位的和相等。
- 全部数字相等且n是偶数时，答案就是n。
- 全部数字相等且n是奇数时，答案通常是n-1，因为去掉任意一个端点后，剩下的偶数长度区间奇偶和刚好相等。
- a[i]很大的情况，比如全为10⁹、n=10⁵，加权前缀和最大能到5×10¹³，必须用long long。
这些边界点我自己在写题时基本都会手动过一遍。把n=1和全相等的情况测过，代码基本就稳了。
6. 提交前必须检查的四个坑：下标、哈希、范围与多组数据
6.1 下标从0开始还是从1开始
题目里的"奇数位置"是指从1开始数的位置。如果你习惯用0下标读数组，判断条件就会变成"下标是偶数时加、下标是奇数时减"，逻辑上多绕一层，特别容易在边界处出错。
我建议读入时直接从1开始存，让数组下标和题面的位置编号完全对应，这样代码最不容易产生歧义。如果一定要用0下标，first[0]就不能初始化为0，而是要初始化为-1，因为s[0]对应的前缀长度是0，位置是-1。这个细节我看不少人踩过。
6.2 用find而不是operator[]判断键是否存在
这是我在代码里特意用find的原因。来看这段错误示范：
if (first[cur] == 0) { // 错误逻辑 }问题在于，unordered_map的operator[]在键不存在时会自动插入一个默认值0。也就是说，cur=5第一次出现时，first[5]被插入为0，然后这个if条件为真，代码会误以为"5之前已经出现过且位置是0"，从而计算出错误长度。更麻烦的是，这个误插入还会影响后续所有判断，排错时非常隐蔽。用find或者count就不会有这种副作用。
6.3 数据范围与哈希表的性能
前缀和的范围很大，所以key必须用long long。value是最早出现的位置，最大n，用int足够。
另外，unordered_map的平均复杂度是O(1)，但最坏情况下可能退化到O(n)。在GESP的评测数据里一般不会被卡，但如果想做得更稳妥，可以用离散化加数组：把扫描过程中所有出现过的cur值收集起来，排序去重后用二分找到下标，再用一个vector 记录每个值第一次出现的位置。这样复杂度是O(n log n)，但完全避开了哈希冲突的问题。这个方法在n特别大的时候也适用。
6.4 多组测试数据时记得清空哈希表
有些题目会要求先输入一个T，表示有T组测试数据。很多人把单组代码改成多组时，最容易忘的就是每次循环都重新初始化unordered_map。
如果偷懒只清空first.clear()，不要忘记重置cur和ans。最安全的方式是直接在while(T--)循环体内部定义哈希表，这样每次循环都是全新对象，彻底杜绝上一组数据残留的问题。
7. 从这道题延伸开：一类"找相等"问题的通用套路
7.1 一个更常见的模板：和为k的最长子数组
"平衡序列"其实是"和为0的最长子数组"问题的变种，只是前缀和的定义从s[i] = s[i-1] + a[i]变成了带奇偶符号的s[i] = s[i-1] + (i为奇数 ? a[i] : -a[i])。
经典的"和为k的最长子数组"是这样：给定数组，求最长的连续子数组，使得子数组和等于k。解法就是维护前缀和cur，在哈希表里查cur - k：
if (first.count(cur - k)) { ans = max(ans, i - first[cur - k]); } if (!first.count(cur)) { first[cur] = i; }你会发现这个结构和平衡序列的代码几乎一模一样，唯一的区别就是"相等"变成了"和等于k"。所以平衡序列这道题本质上考的是一种通法：当区间信息可以用前缀和的差来表达时，就用哈希表记录目标状态的位置，把枚举区间变为查找状态。
7.2 带权前缀和还能怎么考
理解了这种"加权"前缀和的思想，很多变形题你都一眼能看穿：
- 如果是"奇数位置乘积等于偶数位置乘积"，正统做法是对每个数取对数，变成乘积比较转和比较；竞赛里也可以用模大质数的哈希法处理。
- 如果是"差分约束"或"括号匹配"类问题，比如把左括号记为+1、右括号记为-1，前缀和相等的位置之间就是合法括号序列，这和平衡序列是同一个数学结构。
- 如果题目扩展到二维矩阵，让你找一个最大子矩阵满足某种奇偶和条件，思路也是先做列前缀和，再逐行转化为一维问题。
这些变形出现的地方，从GESP四级到CSP-J、CSP-S都有可能。所以别看这道题只是三级的一道编程题，它背后的"前缀和 + 哈希表"组合，是信息学竞赛里几乎绕不开的基础套路。
我自己后来做题，只要遇到"相等""为零""最长的连续区间"这些字眼，第一反应都会先想想能不能用前缀和加一个查找表，把区间枚举问题变成状态查找问题。学会这种思维转换，比背下这一道题的代码重要得多。
