不能直接用双指针或滑动窗口，因为0和1数量相等不构成单调或固定约束；最优解是将0转为-1后转化为前缀和相等问题，用哈希表记录最早前缀和位置，时间O(n)、空间O(n)。
为什么不能直接用双指针或滑动窗口
因为子数组要求「0 和 1 的数量相等」，不是固定值、也不是单调关系，无法通过扩大/缩小窗口来维持某个不变量。暴力枚举所有子数组是 O(n²)，但有更优解——关键在于把问题转换成「前缀和 + 哈希表找最早出现位置」。
- 把每个
0当作-1，1保持为1，那么子数组中 0 和 1 数量相等 ⇔ 子数组和为0 - 进一步：若前缀和
prefix[i]==prefix[j]（i < j），则区间[i+1, j]的和为 0 → 对应原数组中 0 和 1 数量相等
如何用 map 记录最早出现的前缀和位置
用 std::unordered_map<int, int> 存 前缀和 → 最早下标，初始化时插入 0 → -1（表示空前缀和为 0，位置在 -1，方便处理从下标 0 开始的合法子数组）
- 遍历时计算当前前缀和
sum - 如果
sum已存在 map 中，说明从map[sum] + 1到当前下标是一段和为 0 的子数组，长度为i - map[sum] - 否则只记录第一次出现的位置（不覆盖），保证取到最长
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> first;
first[0] = -1; // 空前缀
int sum = 0, maxLen = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += (nums[i] == 1) ? 1 : -1;
if (first.count(sum)) {
maxLen = max(maxLen, i - first[sum]);
} else {
first[sum] = i;
}
}
return maxLen;
}
容易忽略的边界情况
- 输入为空或只有一个元素：函数自然返回
0，无需特判
- 全是
0 或全是 1：前缀和单调增/减，不会重复，结果为 0，正确
- 第一个元素就构成合法子数组（如
[0,1]）：靠 first[0] = -1 支撑，i=1 时 sum=0 已存在，长度 = 1 - (-1) = 2
- 使用
unordered_map 而非 map：避免 O(log n) 开销，整体保持 O(n)
时间与空间复杂度是否可接受
- 时间：单次遍历，O(n)，哈希查找均摊 O(1)
- 空间：最坏情况前缀和全不同，存 n+1 个键值对，O(n)
- 比二维 DP 或暴力前缀和表省空间，也比用 vector 存所有前缀和再二分查找更直接
0，无需特判0 或全是 1：前缀和单调增/减，不会重复，结果为 0，正确[0,1]）：靠 first[0] = -1 支撑，i=1 时 sum=0 已存在，长度 = 1 - (-1) = 2
unordered_map 而非 map：避免 O(log n) 开销，整体保持 O(n)- 时间：单次遍历，O(n)，哈希查找均摊 O(1)
- 空间：最坏情况前缀和全不同，存 n+1 个键值对，O(n)
- 比二维 DP 或暴力前缀和表省空间，也比用 vector 存所有前缀和再二分查找更直接
实际写的时候，别忘了头文件 <unordered_map> 和 <algorithm>；如果编译器较老，first.count(sum) 可换成 first.find(sum) != first.end()。最易错的是忘记初始化 first[0] = -1，会导致漏掉以索引 0 开头的解。
