企业官网建设流程全解析

洛谷P1114这道“非常男女”计划，我第一次读题时还以为是道关于配对的模拟题，点进去才发现它是一道很经典的前缀和练手题，在各大OJ和算法入门清单里都常驻。题目本身不复杂，但能从一个“统计男女数量相等的最长连续区间”的问题里，引出前缀和、哈希映射、数组下标偏移这一整套基础功，非常适合刚学完数组和基础数据结构、准备迈入算法刷题阶段的Java同学。这篇文章我就从题意拆解、核心思路一步步讲到最终代码和踩坑记录，把这道题完整讲透。

1. 题意拆解：这道题到底在求什么

1.1 读懂“非常男女”的隐藏要求

题目给定一个长度为n的序列，序列里每个位置只可能是两个值，一般是0和1，用来表示女生和男生。题目要求找出一段连续的子区间，使得这个区间里0和1的数量一样多，而且这个区间的长度要尽可能长，最后输出最长的长度。

这里有几个容易忽略的关键信息：

• 必须是连续的一段，不是让你随便从序列里挑若干个位置出来拼凑。
• 题目光看输入输出样例，很容易误以为只要找“相邻的一对男女”就行，实际上最少可以是一男一女挨在一起，但也可能是几千个位置组成的大区间。
• 输出的是长度，不是起止位置，更不是方案数。

举个例子，如果序列是1 1 1 0 0 0，男生有三个、女生有三个，而且刚好排在一起，那么整个序列本身就是男女数量相等的区间，长度是6。但如果序列是1 0 0 1 1，你要自己找一找，最长的平衡区间在哪一段，可能是中间的1 0 0 1，也可能是某两个相邻位置，这就要靠算法来统一处理了。

1.2 朴素思路为什么不能直接写

看到这种“找区间”的题，很多人的第一反应和我一样：枚举所有左端点和右端点，然后统计区间里0和1的个数，判断是否相等，记录最大长度。

这种暴力做法的时间复杂度是O(n^2)甚至O(n^3)。如果n比较小，比如几百，那完全没问题；但这类题的数据范围通常会把n推到10^5这个量级，O(n^2)意味着最多要执行约10^10次操作，Java在默认评测环境下根本无法在时限内跑完。

换成更直观的说法：想象有100000个人站成一排，你要检查所有可能的“从第i个到第j个”这些人之间的男女差。每两个人之间都要统计一遍，就算每个人都身怀绝技，这个统计量也太大。所以必须换一种眼光，把“一段人”的信息压缩成某个能快速比较的状态，这正是前缀和能发挥作用的地方。

2. 核心思路：把性别变成数字，问题立刻变简单

2.1 为什么男生记1、女生记-1

前缀和的核心操作，是把一个序列的累积信息存下来。这里的关键技巧是：把题目中的0和1，映射成1和-1。

• 男生（记为1）对前缀和的贡献是 +1
• 女生（记为0）对前缀和的贡献是 -1

用变量sum记录“当前位置之前所有人贡献的总和”。当sum的数值在某两个位置相等时，说明这两个位置之间的那段，+1和-1的数量恰好抵消了，也就是男生数量等于女生数量。

这个思路的本质是：区间内男女数量相等，等价于区间内所有值的和为0。既然要求一段区间的和为0，自然就想到用前缀和来判断。前缀和数组pre[i]表示前i个元素的累加和，那么区间[l, r]的和就是pre[r] - pre[l-1]。要让这个差值为0，只需要pre[r] == pre[l-1]。

所以问题就变成了：在所有前缀和相等的位置对(i, j)中，找出j - i的最大值。

2.2 前缀和相同意味着什么

先看一个具体例子，输入：1 1 1 0 0 0，映射后就是1 1 1 -1 -1 -1。

我手动算一遍前缀和：

• 前1个：sum = 1
• 前2个：sum = 2
• 前3个：sum = 3
• 前4个：sum = 2
• 前5个：sum = 1
• 前6个：sum = 0

注意看，前缀和为2出现在位置2和位置4；前缀和为1出现在位置1和位置5；前缀和为0出现在初始位置（位置0）和位置6。

那么位置2到位置4这一段[1, -1]的和是0，长度2；位置1到位置5这一段[1, 1, -1, -1]的和是0，长度4；位置0到位置6更是整个序列，长度6。答案取最大，就是6。

这个“位置0”非常关键。很多人第一次写的时候容易忽略初始状态：一个元素都还没取的时候，前缀和就是0。如果漏掉它，那么像整段序列本身就平衡的情况就永远统计不到，因为找不到和0相等的另一个前缀和位置。后面写代码时，必须把这个初始状态显式记录进去。

2.3 记录“最早出现位置”还是“哈希表”

现在目标明确：遍历一遍序列，不断更新前缀和sum，然后判断这个sum之前有没有出现过。

如果出现过，假设之前最早出现的位置是first，那么当前位置i到first + 1这一段就是平衡区间，长度是i - first；如果没出现过，就把当前sum和当前位置i存下来。

这里有个细节：应该存“最早出现的位置”，而不是“最近出现的位置”。因为我们要的是最长区间，一旦某个前缀和多处出现，那么最早出现的位置和最晚出现的位置之间肯定跨度最大。所以记录最早位置就够用了，之后遇到同一个sum，只需要用当前位置减去最早位置。

数据结构方面有两种主流选择：

• 用HashMap<Integer, Integer>，键是前缀和，值是最早出现的位置。
• 用一个整数数组，因为sum的取值范围是[-n, n]，总共2n + 1种可能，直接开一个大小为2n + 1的数组，加上偏移量来映射下标。

两种方式都能通过，但在Java里，HashMap会涉及自动装箱、哈希计算和扩容，常数比较大；数组直接按下标访问，速度更稳。这道题n最多10^5，HashMap其实也能过，但如果养成了“能用数组就不上哈希表”的习惯，对后续处理更大数据范围的题目会很有帮助。下面我会把两种版本都写出来，并说明为什么最终选择数组。

3. Java实现：从第一版到最终版

3.1 第一版：用HashMap的直白写法

先给出最符合思维逻辑的版本。这个版本把所有状态都放进了Map里，读起来非常直观，适合用来理解算法本身。

import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); HashMap<Integer, Integer> first = new HashMap<>(); first.put(0, 0); int sum = 0; int ans = 0; for (int i = 1; i <= n; i++) { int x = sc.nextInt(); sum += (x == 1 ? 1 : -1); if (first.containsKey(sum)) { ans = Math.max(ans, i - first.get(sum)); } else { first.put(sum, i); } } System.out.println(ans); } }

这段代码的逻辑就是核心思路的直接翻译：

1. first.put(0, 0)表示在位置0，前缀和为0已经出现过。
2. 每次读一个数，按性别把sum加1或减1。
3. 如果当前sum之前在first里出现过，就拿当前位置减最早位置，更新答案。
4. 如果没出现过，就把当前位置存成这个sum的最早位置。

这里有个容易想错的地方：为什么更新完答案后不把当前sum的位置也更新成i？因为我们要的是最长区间，如果用i覆盖掉最早位置，那么后续再遇到同一个sum时，计算出来的长度只会更短，就永远失去了潜在的最优解。所以只在第一次出现时记录位置，之后一律只用来算长度。

3.2 最终版：用数组映射代替哈希表

理解了HashMap版本之后，再来写出竞赛里更推荐的数组版本。虽然代码稍微长一点，但其实只是多了一个下标偏移的处理。

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; 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()); int[] first = new int[2 * n + 1]; Arrays.fill(first, -1); int offset = n; first[offset] = 0; int sum = 0; int ans = 0; String[] parts = br.readLine().split(" "); for (int i = 1; i <= n; i++) { int x = Integer.parseInt(parts[i - 1]); sum += (x == 1 ? 1 : -1); int idx = sum + offset; if (first[idx] == -1) { first[idx] = i; } else { ans = Math.max(ans, i - first[idx]); } } System.out.println(ans); } }

这里最核心的映射关系是：前缀和sum的范围是[-n, n]，所以我把sum加上偏移量n，得到[0, 2n]范围的下标，正好对应数组first的长度2n + 1。

举个例子：

• sum = 0，对应下标n，first[n] = 0就是初始状态。
• sum = 3，对应下标n + 3。
• sum = -2，对应下标n - 2。

数组first的每个元素一开始都是-1，代表这个前缀和还没有出现过。一旦遇到某个前缀和第一次出现，就把当前位置写进去。之后如果又遇到同一个前缀和，就说明这一段区间男女平衡，更新答案。

3.3 提交前的几个检查点

每次写完代码准备提交时，我习惯快速过一遍这些细节，这道题的坑基本都集中在这里：

• first数组的长度必须是2 * n + 1：因为最极端情况下，前n个全是男生，sum能到n；前n个全是女生，sum能到-n。总共n - (-n) + 1 = 2n + 1个状态。
• first[offset]必须初始化成0：这个offset就是n，对应前缀和0。如果不初始化，整段序列平衡的情况就会漏掉。我实测中确实见过不少人卡在这个点上，样例能过，但提交后某个测试点答案少了一截。
• 数组默认值不能直接用0：因为位置0已经被占用了，如果用0表示“未出现”，那么初始状态sum=0的位置也是0，会混淆。所以统一用-1表示未出现，用Arrays.fill(first, -1)初始化。
• 输入读取：这道题n最多10^5，第二行数据量不大，用BufferedReader加split完全够用。如果后续遇到更大数据范围，可以改成StreamTokenizer或自定义快速输入，但这里没必要。
• 类名必须是Main：在洛谷这类OJ平台提交Java代码时，主类名通常必须叫Main，否则编译阶段就报错。这个细节看起来不起眼，实际提交时却很容易翻车。

4. 复杂度分析与边界情况

4.1 时间复杂度和空间复杂度

整个算法的核心循环只有一次for循环，从位置1遍历到位置n，每次操作都是O(1)：

• 更新sum：一次加法。
• 计算数组下标：一次加法。
• 判断数组值并更新答案：一次比较和一次赋值。

所以时间复杂度是O(n)，无论n多大，只要数据读取跟得上，遍历一遍就能出答案。空间上只用了一个长度2n + 1的数组，也是O(n)。

对比暴力解法的O(n^2)甚至O(n^3)，这个效率提升是很明显的。如果把n看作10^5，暴力可能需要执行上亿次操作，而前缀和方案只需要执行约10万次核心操作，速度差了好几个数量级。

4.2 边界条件最容易踩的坑

这类题目的边界条件经常藏在一些“看起来不用管”的地方。

第一个边界是n = 1。序列只有一个位置，无论它是男是女，都不可能形成平衡区间，答案应该是0。在代码中，sum第一次变到1或-1，对应的数组下标位置是-1，所以只记录不更新答案，最终ans保持0。这个行为是自然的。

第二个边界是序列本身从第一个位置开始就连续平衡。比如1 0 1 0 1 0，最长的平衡区间就是整个序列，长度6。这时候必须保证first[n] = 0这条初始状态生效。我手动跑一遍这个输入：

• i=1，x=1，sum=1，first[n+1]=1
• i=2，x=0，sum=0，idx=n，first[n]不为-1，ans=2-0=2
• i=3，x=1，sum=1，idx=n+1，first存在，ans=3-1=2
• i=4，x=0，sum=0，idx=n，ans=4-0=4
• i=5，sum=1，idx=n+1，ans=5-1=4
• i=6，sum=0，idx=n，ans=6-0=6

遍历完，答案是6。

第三个边界是序列里全是同一种性别。比如1 1 1 1，前缀和是1、2、3、4，没有任何重复，答案保持0。如果全是0 0 0 0，前缀和是-1、-2、-3、-4，同样没有重复，答案也是0。这说明代码不会因为负数下标而崩溃，因为偏移量offset已经把-4映射到n-4这个合法位置了。

4.3 为什么更新答案的时机不能反过来

我见过不少初写者在else分支里也写ans = Math.max(ans, i - first[idx])，这样看起来也没错，但要注意：既然进了else分支，就说明之前这个前缀和出现过，计算出来的i - first[idx]一定是个有意义的候选答案。真正容易出问题的是把逻辑写成：

if (first[idx] == -1) { first[idx] = i; ans = Math.max(ans, i - first[idx]); }

这样写就错误了。因为当某个前缀和第一次出现时，first[idx]刚被设置成i，i - first[idx]恒等于0，永远不会产生正确答案，而且还会把第一次出现的状态错误地当成一种合法区间。这个错误比较隐蔽，因为程序不会报错，只是答案一直偏小。

判断“该不该更新答案”的标准其实只有一个：当前前缀和是否之前已经出现过。如果出现过，才有可能形成非空区间；如果从没出现过，就不可能凭空形成区间。所以答案更新只能放在“已存在”的分支里。

5. 常见卡壳点排查与优化心得

5.1 我实测中遇到的三个问题

这道题我前后给几位同学讲过，他们实际写代码时遇到的问题还挺有代表性，我在这里整理一下。

第一个问题是first数组初始化用了0而不是-1。表面上看，数组默认就是0，省去Arrays.fill这一步，很省事。但问题在于first[n] = 0这个初始状态和“未出现”的标志冲突了。一旦遇到sum=0的情况，程序不知道这是初始状态还是某个未记录的非法状态，或者更严重地，当某个前缀和对应的下标恰好是数组默认值0的位置，会被误判成“已经出现过”，导致计算出错误答案。所以只要用数组记录状态，最好统一默认值并用一个不可能出现的值表示“未出现”，在本题里-1是最合适的，因为位置索引从0开始，任何真实位置都不可能是负数。

第二个问题是边界读取问题。有人用Scanner一行一行读，结果第二行数据可能跨多行，nextInt()本身没问题，但如果用readLine()处理，就需要小心第二行是否存在换行或者空串。我在文章最终版里用的是br.readLine().split(" ")，默认假设所有数据在同一行。如果题目输入格式不保证这一点，更稳妥的方式是直接用Scanner或者StringTokenizer循环读取每个整数，避免跨行问题。这道题的输入一般是一行，但养成用StringTokenizer的习惯能稳妥处理各种空白字符。

第三个问题是对“偏移量”不够理解。有的同学会写成int idx = sum + n + 1，理由是怕sum + n越界。实际上，sum的最小值是-n，加上n得到0；最大值是n，加上n得到2n。数组下标范围是0到2n，sum + n正好覆盖这个范围，不需要再加1。如果多加了1，数组末尾空出一个位置，虽然不影响正确性，但说明没有真正搞懂映射关系。写代码之前最好在纸上画一条数轴，标出-n到n和0到2n的对应关系。

5.2 前缀和状态压缩的通用套路

做完这道题，值得再往深想一层：这种“把区间和转化为前缀和相等”的思路，并不仅仅适用于男女配对问题。

比如题目换成“求最长的一段，其中1比0多k个”，那么条件就变成pre[r] - pre[l-1] = k，也就是pre[r] - k = pre[l-1]。在遍历时，除了记录当前前缀和最早出现位置，还需要额外查询sum - k这个值是否出现过。逻辑完全一致，只是判断条件多了一个偏移。再比如“求最长的一段，使得子段和对某个数取模后等于0”，那就是记录前缀和取模后的值，遇到同样的余数就形成候选区间。这些都是同一个套路的变体。

如果把“男生1女生-1”这个技巧再延伸，还可以处理“只有两类对象、要求数量差为固定值”的问题。背后的本质是：当区间合法性只和区间内两类元素的数量差有关时，就可以利用前缀和把区间问题转化为两个独立位置之间的关系，再用哈希表或数组把O(n^2)降为O(n)。

5.3 关于Java输入输出优化的补充

洛谷这类在线评测平台对Java的时间限制通常比C++宽松一些，但也不是无限宽松。这道题数据范围10^5，用Scanner完全没问题，但如果你准备长期刷题，建议从一开始就习惯使用BufferedReader和BufferedWriter。原因很简单：Scanner在每次读取时做大量格式解析和缓冲区操作，数据量一大就会成为性能瓶颈；而BufferedReader按行读取字符串再手动解析整数，性能稳定得多。

附带提一下输出，如果题目要求输出多行结果，用StringBuilder拼接后一次性输出，比每次System.out.println快非常多。本题只输出一个整数，直接println就好。

结尾

这道“非常男女”计划做完之后，我最大的感受是：很多看似需要枚举区间的题目，一旦想到“用相反数表示两类对象”和“记录前缀和最早出现位置”这两招，复杂度就能瞬间降下来。后来遇到好几个和配对、差值、余数相关的算法题，我都会下意识地想，能不能把问题转换成前缀和相等或前缀和差固定的形式。这个思维习惯带来的收益，远不止P1114这一道题。

最后再分享一个实战中的小建议：第一次写这道题时，不要急着看题解，先在草稿纸上手动模拟几组小数据。比如自己写一个1 0 1 0，画出前缀和的变化过程，标出每个sum第一次出现的位置，你会比我讲任何理论都更直观地理解为什么first[n] = 0不能丢，为什么答案要更新在“已存在”的分支里。把这些手感练出来了，以后再遇到前缀和的题，你就能少走很多弯路。