你好！我是你的OI竞赛教练。这道题（LeetCode 525）是非常经典的前缀和与哈希表结合的题目。

---

一、 题目描述（OI风格改编）

题目名称：01平衡区间 (01 Balance)

【题目背景】 在一段由 0 和 1 组成的数字信号流中，我们希望找到一段最长的连续区间，使得该区间内 0 的数量和 1 的数量完全相等，以便进行信号校准。

【题目描述】 给定一个长度为 $N$ 的二进制数组 nums，数组中只包含 $0$ 和 $1$。 请你找到该数组中满足“0 的数量和 1 的数量相等”的最长连续子数组的长度。

【输入格式】 第一行包含一个整数 $N$，表示数组的长度。 第二行包含 $N$ 个整数，表示数组 nums 的元素，中间用空格隔开。

【输出格式】 输出一个整数，表示满足条件的最长连续子数组的长度。如果不存在，输出 0。

【数据范围】 $1 \leq N \leq 10^5$ nums[i] 为 $0$ 或 $1$。

【样例输入】

7
0 1 0 1 1 1 0

【样例输出】

4

(解释: 最长子数组是 [0, 1, 0, 1] 或 [0, 1, 1, 1, 0] 中的 [1, 0] 等等... 等等，稍微修正一下样例解释: [0, 1, 0, 1] 长度4，[0, 1] 长度2。输入样例里最长的是前四个 0 1 0 1，或者后四个 1 1 0 (不平衡) ... 实际上样例是前4个，或者中间的 1 0 1 (不平衡)... 让我们手动推一下样例: 0 1 0 1 1 1 0 前缀和(-1, 1): -1, 0, -1, 0, 1, 2, 1 最长的是 0 1 0 1 (长度4)。 )

---

二、 预备知识点

解决这道题，你需要熟练掌握以下工具：

1. 前缀和 (Prefix Sum)：用于快速计算区间和。
2. 哈希表 (Hash Map) / 计数数组：用于记录状态第一次出现的位置，实现 $O(1)$ 查询。
3. 等价转换思想：将“计数相等”转换为“数值求和为0”。

---

三、 启发式教学与思路推演

来，拿出草稿纸，我们画图来理解这道题。

1. 朴素思路（暴力法）

如果让你直接做，你会怎么做？

• 学生：枚举所有可能的子数组 $nums[i...j]$，数里面的0和1，如果相等就更新最大长度。
• 教练：很好。但是有 $N^2$ 个子数组，每次数数又要 $O(N)$（或者用前缀和优化到 $O(1)$），总复杂度是 $O(N^2)$。当 $N=10^5$ 时，计算量高达 $10^{10}$，肯定会 TLE (Time Limit Exceeded)。我们需要 $O(N)$ 的做法。

2. 关键转化（破题点）

题目要求：0的个数 == 1的个数。 这个条件不太好直接算数学和。能不能改写一下数组里的数字，让“个数相等”变成一个更简单的数学性质？

• 提示：如果把 $0$ 变成 $-1$，把 $1$ 保持为 $1$。
• 推演：那么一段区间里 0 和 1 个数相等，意味着这段区间的元素之和等于多少？
• 结论：区间和为 0。

3. 引入前缀和（图形化思考）

定义 sum 为从数组开始到当前位置的累加和（$0$ 变 $-1$，$1$ 变 $1$）。

让我们画出 sum 随下标 i 变化的折线图： 假设输入：[0, 1, 0, 1, 1, 1, 0] 变换后：[-1, 1, -1, 1, 1, 1, -1]

i (下标)	nums[i]	变换值	当前前缀和 (sum)	草稿纸上的思考
初始			0	重要：还没开始走，和是0，下标看作-1
0		-1		第一次出现 -1，记下位置 0
1			0	和变回 0 了！说明 nums[0...1] 和为0。长度 $1 - (-1) = 2$
2	0	-1	-1	和又是 -1！上次 -1 在位置 0。说明 nums[1...2] 抵消了。长度 $2 - 0 = 2$
3	1		0	和又是 0！上次 0 在位置 -1。长度 $3 - (-1) = 4$。更新最大值！
4			1	第一次出现 1，记下位置 4
5			2	第一次出现 2，记下位置 5
6	0	-1	1	和是 1！上次 1 在位置 4。长度 $6 - 4 = 2$。不更新。

4. 核心逻辑推导

• 如果我们计算出当前的前缀和是 S。
• 如果我们之前在下标 j 的时候，前缀和也是 S。
• 这意味着什么？
  • PreSum[current] = S
  • PreSum[j] = S
  • 中间这一段 (j, current] 的和 = PreSum[current] - PreSum[j] = $S - S = 0$。
• 贪心策略：为了让长度最长，对于同一个前缀和值 $S$，我们应该保留它第一次出现的下标 j。后面再遇到 $S$ 时，直接用 current - j 算长度。

5. 复杂度分析

• 时间复杂度：我们需要遍历数组一次。每次查哈希表是 $O(1)$。总共 $O(N)$。完美！
• 空间复杂度：哈希表最多存 $N$ 个不同的前缀和。$O(N)$。

---

四、 读题关键词总结

做这类题时，看到以下关键词要形成条件反射：

1. “连续子数组” (Contiguous Subarray) $\rightarrow$ 想到 前缀和 (Prefix Sum) 或 滑动窗口。
2. “数量相等” / “和为 K” $\rightarrow$ 想到 前缀和 + 哈希表（两数之差问题）。
3. “0 和 1” $\rightarrow$ 想到 赋值转换（$0 \to -1$），将计数问题转化为求和问题。

---

五、 OI风格 C++14 代码范例

这里提供一份符合竞赛标准的题解代码。

注意点：

1. 使用了 std::unordered_map 来记录 前缀和 -> 第一次出现的下标。
2. 初始化非常关键：mp[0] = -1;。这代表在数组还没开始前，前缀和为0，位置虚拟为-1。如果不加这行，从头开始的有效子数组（如 [0, 1]）会被漏判。
3. 使用了 ios::sync_with_stdio(0) 加速 I/O，这是竞赛基本功。

/**
 * 题目：01平衡区间 (LeetCode 525 改编)
 * 算法：前缀和 + 哈希表
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 */

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 核心解题函数
int solve() {
    int N;
    if (!(cin >> N)) return 0;
    
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

    // 哈希表：key = 前缀和, value = 该前缀和第一次出现的下标
    unordered_map<int, int> mp;
    
    // 初始化：前缀和为0出现在下标-1处
    // 这一步是为了处理从数组下标0开始就满足条件的子数组
    mp[0] = -1;

    int current_sum = 0;
    int max_len = 0;

    for (int i = 0; i < N; ++i) {
        // 核心转化：0 变成 -1，1 还是 1
        int val = (nums[i] == 0) ? -1 : 1;
        current_sum += val;

        // 检查当前前缀和是否之前出现过
        if (mp.count(current_sum)) {
            // 如果出现过，说明从 上次出现位置+1 到 当前位置 的子数组和为 0
            // 即 0 和 1 数量相等
            int prev_index = mp[current_sum];
            max_len = max(max_len, i - prev_index);
        } else {
            // 如果没出现过，记录下来。
            // 只记录第一次出现的位置，因为我们要找最长的，下标越靠左越好
            mp[current_sum] = i;
        }
    }

    return max_len;
}

int main() {
    // 竞赛常用 I/O 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve() << endl;

    return 0;
}

进阶优化思考（留给学生的作业）

如果 $N$ 很大但内存很紧，而且题目告诉你是单纯的 0/1 转换，$sum$ 的范围其实在 $[-N, N]$ 之间。

• 你能否用数组 (Array) 代替 unordered_map 来进一步提升常数级的速度并避免哈希冲突？
• 提示：数组下标不能是负数，可以通过 offset = N 将下标平移到 [0, 2N]。

希望这个辅导对你有帮助！在纸上把那个表格自己推一遍，你就彻底懂了。