在洛谷刷到 P1114“非常男女”计划 的时候，第一反应是这题名有点意思。它本质上是一个 0/1 序列的区间问题：一排人，每个位置要么是男生要么是女生，要求找出一段连续的子排队，使得这一段里面男生数量和女生数量完全一样，输出最长的长度。题面本身不绕，但如果你直接按字面去枚举区间，这道题会变成一场灾难。这篇文章我打算把完整的拆解思路、Java 实现、以及我实际调试时踩过的坑都写清楚，适合准备入门前缀和、或者在这道题上 WA 过几次的选手参考。
1. 破题思路：从题面到数学模型的两次翻译
1.1 题目到底在说什么
先别急着写代码，把已知条件列出来。
第一，序列里元素类型只有两种，不是男生就是女生；第二，要求的是连续子区间，不能随便挑人；第三，目标是区间长度最大化。这三个特征放在一起，基本就是把题目往“前缀和”方向推的信号。
这里有个地方容易忽略：题目说的是“连续”。如果没有连续这个限制，那直接统计整排有多少男生多少女生，取个偶数输出就完事了。连续的存在，让问题变成了典型的区间子段问题。再看一眼数据范围，n 到十万级别，你要是敢在第二层循环里枚举区间，等你的必然是超时。
所以读题之后第一件事不是开 IDE，而是确认两个东西：输入格式是“0/1 字符串”还是“用空格分隔的整数”，以及 n 的上限。这两个信息决定后面代码怎么写，后面踩坑部分我会专门展开。
1.2 暴力枚举为什么不可行
小白的通病是看到“最长区间”就第一时间枚举左右端点。外层循环枚举左端点，内层循环枚举右端点，再对每个区间统计一遍男生女生数量。这种解法的复杂度是 O(n³)。稍微优化一步，预处理一个“到当前位置为止男生数量”的前缀数组，任意区间内男生数量可以在 O(1) 时间算出来，复杂度可以降到 O(n²)，但依然过不了十万数据。
十万的平方是一百亿次操作，哪怕一次操作只是一个简单的加法，在评测机上也要跑好几十秒。所以这道题就逼着你去找一个接近单次扫描的线性做法。
这里我放一张直观的复杂度对比表：
| 方案 | 复杂度 | n=100000 时能过吗 |
|---|---|---|
| 暴力枚举区间 + 逐段统计 | O(n³) | 不可能 |
| 前缀计数 + 枚举所有区间 | O(n²) | 超时 |
| 前缀和 + 首次下标记录 | O(n) | 可以 |
1.3 核心转化：用“+1/-1”把平衡问题变成回原点问题
这是整道题最关键的跳跃。假设你从第一个人开始维护一个变量 cur：遇到男生让 cur 加 1，遇到女生让 cur 减 1。想象你站在一条数轴上，男生向右迈一步，女生向左迈一步。那么“一段连续区间里男女数量相等”意味着什么？
意味着这段路程走完之后，你又回到了起点。向右一步和向左一步相互抵消，位移为零。这个“位移为零”的观察，是破题的钥匙。
用数学语言写出来就是：给每个男生赋权值 +1，每个女生赋权值 -1，那么一个区间男女数量相等，等价于这个区间的权值和为 0。而一个区间的权值和为 0，又等价于这个区间左右端点处的前缀权值和相等。后一句是整个算法的核心，下一章我单独展开讲。
2. 前缀和与区间和：为什么“相等前缀和”能精准命中答案
2.1 把“经过的位置”写成前缀和序列
定义prefix[0] = 0，然后prefix[i] = prefix[i-1] + delta[i]，其中delta[i]是第 i 个人的权值，男生取 +1，女生取 -1。
举个例子，序列1 0 1 1 0 0（1 代表男生，0 代表女生），对应的 delta 是+1 -1 +1 +1 -1 -1，前缀和序列就是：
0, 1, 0, 1, 2, 1, 0现在要判断区间[l, r]内男女是否相等，不需要再遍历这个区间，只需要检查prefix[r] - prefix[l-1]是否等于 0。如果等于 0，说明这个区间内正负权值完全抵消，男生女生数量相等。
进一步变换，条件变成prefix[r] == prefix[l-1]。
也就是说，我们不再关心区间内部长什么样，只关心区间两端对应的前缀和值是否相同。这是一个巨大的降维：区间有 O(n²) 个，但前缀和只有 O(n) 个。你理解到这里，这题已经解了一大半。
2.2 一个小例子的完整推演
继续用上面的例子：
前缀和序列：0, 1, 0, 1, 2, 1, 0看一下前缀和值 0 出现的位置：下标 0、2、6。最远距离是 6 - 0 = 6，对应区间就是整个序列1 0 1 1 0 0，里面正好 3 个男生 3 个女生，答案先记为 6。
再看前缀和值 1 出现的位置：下标 1、3、5。最远距离是 5 - 1 = 4，对应区间[2, 5]，内容是0 1 1 0，也是 2 男 2 女。
答案是 6。整个推导过程的核心就一句话：找到前缀和序列中，同一个值出现的最远距离。
2.3 为什么只需要记录第一次出现的位置
有人可能会问：前缀和值可能多次出现，怎么快速求出最远距离？
答案很简单。对于一个固定值 v，最远的一对一定是最早出现的位置和最后一次出现的位置。你只需要从左到右扫描一遍，遇到 v 第一次出现就把下标记下来，之后每次再遇到 v，用当前位置减掉最早位置，得到候选答案，更新全局最大值。
不需要统计 v 出现过多少次，不需要记录出现频次，也不需要排序。这个“只记最早出现位置”的小技巧，就是算法能压到 O(n) 的最后一环。
还有一个细节必须提醒：前缀和序列的下标是从 1 到 n，但prefix[0] = 0也是一个真实存在的位置，它代表第 1 个人出现之前的状态。写代码时这个 0 位置特别容易丢，丢了就会出一类很隐蔽的错，后面踩坑部分我会复盘。
3. Java 实现细节：从负数下标到初始化陷阱
3.1 负下标用偏移量解决
前缀和的值范围是[-n, n]。全是女生时，cur 一直减，最小到 -n；全是男生时，最大到 n。但 Java 数组下标必须是非负的。
处理方法很朴素：给每个前缀和值都加上 n，映射到[0, 2n]。数组长度开2n + 1就刚刚好。
我以前写这类题总是习惯用HashMap<Integer, Integer>存第一次出现位置，也能过，但后来发现没必要。值域连续、范围已知、只有十万级别，用 int 数组比 HashMap 快不少，还能省掉自动装箱的额外开销。数据量一大，这个常数差异会体现出来。
3.2 first 数组的初始化陷阱
first 数组的初值建议设成-1，表示“尚未出现”。为什么不能设成 0？因为下标 0 会被prefix[0] = 0占用。如果你把初值设成 0，就会和prefix[0]的位置冲突，逻辑直接乱掉。
真正关键的一步是：在扫描开始之前，先执行first[n] = 0，表示前缀和值 0 在下标 0 这个位置已经出现过一次。
这一步是很多第一次写这题的人会漏掉的。没有了它，整个序列恰好男女平衡、答案应该是 n 的用例，会算出一个偏小的值。后面第 4 章我会用具体数据演示这个坑到底有多隐蔽。
3.3 循环体的更新顺序
遍历每个人时，先更新 cur，再计算idx = cur + n。如果first[idx] == -1，说明这个前缀和值是第一次遇到，记录first[idx] = i；否则，用i - first[idx]更新答案。
一个值得强调的顺序问题：首次遇到某个前缀和值时，千万别顺手就更新答案，那只能得到 0，没有任何意义。首次遇到要做的是记录，后续遇到才是计算。
另外，不要写成i - first[idx] + 1。原因我在踩坑部分专门讲，这里先记住结论。
3.4 完整可提交的 Java 代码
假设输入格式是：第一行一个整数 n，第二行是一个长度为 n 的 0/1 字符串，下面这版代码可以直接提交。
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String s = br.readLine().trim(); int[] first = new int[2 * n + 1]; Arrays.fill(first, -1); int cur = 0; first[n] = 0; // 关键：prefix[0] = 0 int ans = 0; for (int i = 1; i <= n; i++) { if (s.charAt(i - 1) == '1') { cur++; } else { cur--; } int idx = cur + n; if (first[idx] == -1) { first[idx] = i; } else { ans = Math.max(ans, i - first[idx]); } } System.out.println(ans); br.close(); } }如果你的题目输入格式是“第二行有 n 个空格分隔的整数”，那就不要用charAt(i-1)去取字符，否则会把空格当成 0 处理，所有数据都跑偏。这种情况可以改成用StringTokenizer逐个数读取，循环体里的判断逻辑不变。
提示：
first[n] = 0这一行必须在循环前执行。它代表“前缀和值 0 最早在下标 0 出现”，整个算法的心脏就在这一行。
3.5 复杂度分析
时间上每个字符只处理一次，O(n)。空间上开了一个长度2n + 1的 int 数组，O(n)。n 为十万时，数组长度二十万出头，内存占用 1MB 上下，非常安全。
这也是为什么这道题适合用数组而不是 HashMap：值域连续且闭区间已知，数组天然就是最合适的哈希表。如果你顺着这个思路再看其他前缀和题，会发现很多都能用数组替代 map，写出更干净的解法。
4. 我踩过的坑：调试过程复盘
4.1 漏掉 prefix[0] 导致的“样例全过但数据一构造就挂”
这个坑我印象非常深。样例数据比较简单，跑出来答案是对的，但自己构造了一个全平衡序列1010，正确答案应该是 4，结果代码输出 2。
我逐步打印前缀和序列：0, 1, 0, 1, 0。一眼就发现问题了：前缀和值 0 最早出现在下标 0，但 first 数组里根本没有记录下标 0，所以第一次遇到“值 0”被记成了下标 2。之后到下标 4 再次遇到值 0，算出来的长度是 4 - 2 = 2，而不是正确的 4 - 0 = 4。
排查方法很简单：把前缀和序列打印出来，人眼扫一遍就会发现“最早位置”没记对。修复方式就是在循环前补一行first[n] = 0。
如果你的代码样例能过，但自己构造“整个序列刚好男女平衡”的数据就出错，先检查这一行。
4.2 区间长度写成 i - first + 1 的经典错误
另一个高频错误是把答案更新写成i - first[idx] + 1。为什么会多出来一个 1？因为 first 记录的不是区间左端点，而是左端点前一个位置，也就是l - 1。
设区间是[l, r]，前缀和相等条件是prefix[r] == prefix[l-1]。区间长度是r - (l-1)，也就是当前下标 i 减去 first 数组里存的位置。如果写成i - first + 1，就多加了 1。
最简单验证方法就是拿序列10去试：男生 +1，女生 -1，i=2 时 cur=0，正确答案是 2。加 1 得到 3，明显违反常识。做题时一定要回到定义去推，别凭感觉套公式。
4.3 输入格式的隐形坑
有一类题目版本输入是：第一行 N，第二行 N 个整数，用空格隔开。如果你按无空格字符串来处理，charAt会命中空格字符，它既不是'1'也不是'0'，于是每个空格都走了 else 分支，把所有人都当成女生。前缀和一路往负方向跑，答案自然是错的。
解决方式只有一种：写代码前先花十秒确认输入格式。如果题目描述是“第二行包含 N 个整数”，就逐个数读取；如果给的是“0/1 组成的字符串”，就用charAt。核心计算逻辑完全一样，但读入层对不上，代码就跑不出正确答案。
下面这个表可以帮你快速自查：
| 输入形式 | 读入方式 | 循环内取数方式 |
|---|---|---|
| 一行 0/1 字符串 | br.readLine() | s.charAt(i-1) |
| 空格分隔的 N 个整数 | StringTokenizer或按空格 split | 逐个转成 int |
4.4 不确定数据范围时的防御性写法
如果题目没有明确说 n 最多是多少，只要内存允许，直接开2n + 1数组就好。n 到一百万时数组依然很轻松；如果要到一千万，八十多 MB 的内存可能有点悬，那时可以考虑用 HashMap 或者坐标压缩。
我的建议是：先看数据范围，n 在百万级别以内直接用数组。实在不确定就写 HashMap，逻辑完全等价，只是常数略大。P1114 这题用数组是绰绰有余的。
5. 从 P1114 到一类题：前缀和思想还能这么扩展
5.1 抽象成“和为 0 的最长连续子段”
刷题多了之后你会发现，P1114 的解法并不是某个孤立的技巧，而是一个更大的套路：给定一个数组，求满足“子段和为 0”的最长连续子段长度。P1114 只是把这个数组里的数替换成了每个人对应的 +1 或 -1。
这个套路的关键三步：
- 构造前缀和数组
- 用哈希表或数组记录每个前缀和第一次出现的位置
- 后续遇到相同前缀和时更新答案
三步走完，任何“区间加权和为某个定值”的题都可以用同一套框架处理。这也是我为什么觉得这题值得写一篇题解，因为它的迁移价值远大于题目本身。
5.2 变式：男生比女生多 k 个
如果题目改成“求最长的区间，使得区间内男生比女生多 k 个”，推导过程几乎一样：
prefix[r] - prefix[l-1] = k也就是要找两个下标，使得后一个前缀和比前一个大 k。实现上仍然扫描 prefix，但更新答案时不再要求prefix[i] == prefix[j]，而是判断prefix[i] - k是否已经出现过。如果出现过，候选答案就是i - first[prefix[i] - k]。
整个框架没有本质变化，只是哈希表里多了一个 k 的偏移。这类变式题很多，你只要把 P1114 吃透，再见到它们会非常轻松。
5.3 变式：值域不连续怎么办
有些题目的前缀和不一定落在[-n, n]，比如规定的差值上限很大，或者值域非常稀疏，数组就不能无脑开了。这时可以选择HashMap<Integer, Integer>，代码写法几乎一样，只是把数组下标换成 map 的 key。
如果担心 HashMap 性能，还可以先把前缀和值排序并离散化，再用数组。但就 P1114 而言，数组直接搞定，没必要绕弯。理解离散化思想却是值得的，因为它在值域很大的前缀和题目里是非常常见的优化手段。
5.4 边界：什么时候不能直接套用
还有一个值得想清楚的问题：为什么这类题要求“两类元素相等”？如果出现了第三类元素，编码方式就要重新设计。再有，如果统计的不再是“数量相等”，而是“某种元素出现次数占比超过一半”，+1/-1 编码会失效，因为正负抵消并不等价于数量优势。
所以看到“相等”“差为定值”这类词时，优先想 ±1 编码；看到“众数”“绝对优势”时，就要换思路，比如摩尔投票一类的方法。知道套路适用的边界，比多刷十道题还重要。
6. 一点刷题之外的个人体会
我刷这题时最大的感受是：把生活化的问题翻译成数学语言，往往是解题中最难也最有价值的一步。P1114 的题面给你一排小朋友、男生女生，如果你一直停留在“男生、女生”这个叙事里，很难想到给它们贴一个“+1/-1”的标签。但是一旦完成编码，后面的前缀和、first 数组就都水到渠成了。
另一个体会是写 OJ 代码时别迷信高级数据结构。这道题用数组代替 HashMap，代码量更短，运行更快，理解起来也更直观。很多时候不是要用多酷炫的算法，而是把你已有的知识组合对。
如果你正在学前缀和相关内容，我建议做完 P1114 之后，自己动手编几个测试数据验证一下 first 数组的逻辑。把序列打乱、全男、全女、正好交替、只有一个元素，这些边界都跑一遍。跑完你会对“下标偏移”和“初始位置 0”有非常深的肌肉记忆。以后再见到任何“区间和为 0 / 为 k”的题，你的第一反应就会是：哦，又是一道 P1114。
