前缀和与哈希表实战：洛谷P1114最长相等子序列问题解析

GESP C++ 五级/四级练习题，一维前缀和与哈希表（或数组映射）的综合应用。题目难度适中，非常适合练习将实际问题抽象为数学模型的能力，对应洛谷难度等级普及-。

题目要求

题目描述

近来，初一年的XXX小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。

万圣节来临之际，XXX准备在学校策划一次大型的 “非常男女” 配对活动。对于这次活动的参与者，XXX有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，XXX当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入格式

第一行有一个正整数 n，代表学校的人数 n。
第二行有 n 个用空格隔开的数，这些数只能是 0 或 1，其中，0 代表是一个女生，1 代表是一个男生。

输出格式

输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子区间的长度。
如果不存在男女人数相等的子区间，请输出 0。

输入输出样例 #1

输入 #1

9
0 1 0 0 0 1 1 0 0

输出 #1

6

题目分析

这道题目的核心是在一个只包含 0 和 1 的序列中，找到一个最长的连续子序列，使得在这个子序列中，0 的数量等于 1 的数量。

1. 问题转化：0 和 1 变 -1 和 1

直接去统计一段区间内的 0 和 1 的个数比较直观，但难以用高效的数学公式表达。我们可以利用权值转化的思想：

• 把题目中的 0 (女生) 看作 -1。
• 把题目中的 1 (男生) 看作 1。

这样一来，“男女人数相等”这个条件就等价于：该连续子序列的所有元素之和为 0（因为 +1 和 -1 会相互抵消）。

2. 前缀和的数学原理

我们定义 sum[i] 为序列中前 i 个人的数值之和（转化后的 -1 和 1 的累加）。

• sum[0] = 0 (初始状态，没有选人，和为 0)
• sum[i] = sum[i-1] + val[i]

根据前缀和的性质，任意一个连续子区间 (j, i]（即从第 j+1 个元素到第 i 个元素）的和可以表示为：
区间和 = sum[i] - sum[j]
我们的目标是找到一个子区间，使其和为 0：
sum[i] - sum[j] = 0 => sum[i] = sum[j]

结论： 只要找到两个不同的位置 i 和 j，使得它们的前缀和 sum[i] 等于 sum[j]，那么这两个位置之间的区间 (j, i]，长度为 i - j）就满足“男女人数相等”。这类问题通常可以归类为经典的算法与数据结构应用。

3. 算法思路推导

为了找到最长的子区间，我们需要让 i - j 最大。

• 当我们遍历到某个位置 i，计算出当前的 sum[i]。
• 我们希望找到一个最小的下标 j (j < i)，使得 sum[j] == sum[i]。

因此，算法策略如下：

1. 记录首次出现的位置：我们需要一个数组（或哈希表）来记录每一个前缀和数值第一次出现的下标。记为 first_pos。
2. 初始化：
   • first_pos 数组初始化为一个特殊值（如 -1），表示该前缀和尚未出现过。
   • 关键点：sum 为 0 的情况在通过第 0 个人时就已经存在了（即空序列），其下标为 0。所以初始化 first_pos[0] = 0。
3. 遍历序列（i 从 1 到 n）：
   • 计算当前的前缀和 current_sum。
   • 查询：检查 current_sum 是否在 first_pos 中出现过。
     • 情况 A：出现过。说明之前有一个位置 j 的前缀和也是 current_sum。那么区间 (first_pos[current_sum], i] 的和为 0。计算长度 len = i - first_pos[current_sum]。如果 len 比当前记录的最大长度 max_len 大，则更新 max_len。注意：此时不要更新 first_pos，因为我们要保留最早出现的下标以获得最长长度。
     • 情况 B：没出现过。这是该 current_sum 第一次出现，记录下来：first_pos[current_sum] = i。

4. 模拟演示 (Dry Run)

以样例输入 9 个人：0 1 0 0 0 1 1 0 0 为例。
转化数值：-1, 1, -1, -1, -1, 1, 1, -1, -1

步骤 i	输入值	当前和 (Sum)	first_pos 状态 (仅列出相关)	操作
0	-	0	pos[0] = 0	初始状态
1	0 (-1)	-1	pos[-1] = 1	-1 首次出现，记录下标 1
2	1 (+1)	0	pos[0] = 0 (已存在)	0 出现过。长度 = 2-0=2。max_len=2
3	0 (-1)	-1	pos[-1] = 1 (已存在)	-1 出现过。长度 = 3-1=2。max_len=2
4	0 (-1)	-2	pos[-2] = 4	-2 首次出现，记录下标 4
5	0 (-1)	-3	pos[-3] = 5	-3 首次出现，记录下标 5
6	1 (+1)	-2	pos[-2] = 4 (已存在)	-2 出现过。长度 = 6-4=2。max_len=2
7	1 (+1)	-1	pos[-1] = 1 (已存在)	-1 出现过。长度 = 7-1=6。max_len=6
8	0 (-1)	-2	pos[-2] = 4 (已存在)	-2 出现过。长度 = 8-4=4。max_len=6
9	0 (-1)	-3	pos[-3] = 5 (已存在)	-3 出现过。长度 = 9-5=4。max_len=6

最终输出：6。

5. 细节处理：负数下标

前缀和 sum 可能是负数（例如连续都是 0，sum 就是 -1, -2, -3...）。在 C++ 中，数组下标不能是负数。
由于最大 n 为 10^5，前缀和的范围在 [-n, n] 之间。为了能用数组存储，我们需要加一个偏移量 (Offset)。令 OFFSET = 100000。

• 存 sum 时，存入 first_pos[sum + OFFSET]。
• 查 sum 时，查 first_pos[sum + OFFSET]。

示例代码

#include <cmath>
#include <iostream>
#include <algorithm>

// current_sum 数组：存储到当前位置 i 为止的前缀和。
// 这里的 i 是从 1 到 n，所以大小为 n+1。
// n 最大 10^5，所以 100005 足够。
int current_sum[100005];

// first_pos 数组：用于记录某个“前缀和”数值第一次出现的下标位置。
// 因为前缀和可能为负数，范围在 -n 到 +n 之间。
// n 最大 10^5，所以范围是 [-100000, 100000]，总共 200001 种可能的值。
// 数组大小 200005 足够覆盖这个范围，并通过偏移量映射到非负下标。
int first_pos[200005];

// 定义偏移量 OFFSET
// 作用：将负数前缀和映射到数组的非负下标。
// 例如，如果前缀和为 -5，在数组中访问 first_pos[-5 + OFFSET]。
const int OFFSET = 100000;

int main() {
    // n：表示学校的人数
    int n;
    // 从标准输入读取人数 n
    std::cin >> n;

    // 循环读取 n 个学生的性别 (0 或 1)，并计算前缀和
    // i 从 1 开始，与题目描述的序列下标习惯一致
    for (int i = 1; i <= n; i++) {
        int num; // 用于存储当前学生的性别 (0 或 1)
        std::cin >> num; // 读取当前学生的性别

        // 核心转化：将 0 (女生) 视为 -1，将 1 (男生) 视为 +1。
        // 这样“男女人数相等”就等价于“区间和为 0”。
        if (num == 0) {
            num = -1;
        }

        // 计算到当前位置 i 的前缀和
        // current_sum[i] = current_sum[i-1] + (当前学生的转化值)
        current_sum[i] = current_sum[i - 1] + num;
    }

    int max_len = 0; // 初始化最长平衡子区间的长度为 0

    // 初始化 first_pos 数组：将所有位置填充为 -1。
    // -1 表示该前缀和数值尚未出现过。
    std::fill(first_pos, first_pos + 200005, -1);

    // 初始状态设置：
    // 还没开始读入数据时 (即在第 0 个位置之前)，前缀和为 0。
    // 这很重要：如果后续某个位置 i 的前缀和 current_sum[i] 再次变为 0，
    // 那么从序列的开始到位置 i 的这段区间 (长度为 i) 就是一个平衡区间。
    // first_pos[0 + OFFSET] 存储的是前缀和为 0 第一次出现的下标，即 0。
    first_pos[0 + OFFSET] = 0;

    // 再次循环遍历计算出的前缀和数组 (从第一个学生开始)
    for (int i = 1; i <= n; i++) {
        // 计算在 first_pos 数组中的实际索引（加上偏移量，转为非负数）
        int index = current_sum[i] + OFFSET;

        // 检查这个前缀和是否之前出现过
        if (first_pos[index] == -1) {
            // 情况 B：如果这个前缀和是第一次出现
            // 记录当前的下标 i。
            first_pos[index] = i;
        } else {
            // 情况 A：这个前缀和之前出现过！
            // 计算当前平衡子区间的长度：当前下标 i - 第一次出现的下标 first_pos[index]
            // 并用 std::max 更新最长长度
            max_len = std::max(max_len, i - first_pos[index]);
        }
    }

    // 输出最终找到的最长平衡子区间的长度
    std::cout << max_len << std::endl;

    return 0;
}

---