LeetCode 525中等前缀和/哈希
连续数组 图解题解
这道题到底在问什么
给定二元数组 nums（只含 0 和 1），返回 0 与 1 数量相同的最长连续子数组的长度；不存在返回 0。
- 输入
- nums=[0,1]
- 输出
- 2（0 和 1 各一个）
- 输入
- nums=[0,1,0]
- 输出
- 2（[0,1] 或 [1,0]）
最优解：一步一步想明白
- 3记住「0 当 −1 求前缀和；同一个 diff 再现 → 之间 0/1 等量」，下面每帧都在套它。
- 4开局把「空前缀」记下：diff=0 出现在下标 −1。这样若某天 diff 回到 0，就知道从开头到那里整段平衡。0 当 −1、1 当 +1 来累加。
- 5读第 0 位 1，把它当 +1 累进前缀差：diff 从 0 变成 1。下一步看这个 diff 以前见过没。
- 6diff=1 是第一次出现，把它的最早下标记进哈希表 first[1]=0（黄色新行）。只记最早的，这样以后算的段才最长。
- 7读第 1 位 1，把它当 +1 累进前缀差：diff 从 1 变成 2。下一步看这个 diff 以前见过没。
- 8diff=2 是第一次出现，把它的最早下标记进哈希表 first[2]=1（黄色新行）。只记最早的，这样以后算的段才最长。
- 9读第 2 位 0，把它当 −1 累进前缀差：diff 从 2 变成 1。下一步看这个 diff 以前见过没。
- 10diff=1 以前出现过（最早在下标 0）！说明下标 1…2 这段（绿色）0 和 1 一样多，长 2。比旧的最长更长，刷新 best=2。
- 11读第 3 位 1，把它当 +1 累进前缀差：diff 从 1 变成 2。下一步看这个 diff 以前见过没。
- 12diff=2 以前出现过（最早在下标 1）！说明下标 2…3 这段（绿色）0 和 1 一样多，长 2。没超过当前最长 2，保持。
- 13读第 4 位 0，把它当 −1 累进前缀差：diff 从 2 变成 1。下一步看这个 diff 以前见过没。
- 14diff=1 以前出现过（最早在下标 0）！说明下标 1…4 这段（绿色）0 和 1 一样多，长 4。比旧的最长更长，刷新 best=4。
- 15读第 5 位 0，把它当 −1 累进前缀差：diff 从 1 变成 0。下一步看这个 diff 以前见过没。
- 16diff=0 以前出现过（最早在下标 -1）！说明下标 0…5 这段（绿色）0 和 1 一样多，长 6。比旧的最长更长，刷新 best=6。
- 17读第 6 位 1，把它当 +1 累进前缀差：diff 从 0 变成 1。下一步看这个 diff 以前见过没。
- 18diff=1 以前出现过（最早在下标 0）！说明下标 1…6 这段（绿色）0 和 1 一样多，长 6。没超过当前最长 6，保持。
- 19读第 7 位 0，把它当 −1 累进前缀差：diff 从 1 变成 0。下一步看这个 diff 以前见过没。
- 20diff=0 以前出现过（最早在下标 -1）！说明下标 0…7 这段（绿色）0 和 1 一样多，长 8。比旧的最长更长，刷新 best=8。
- 21读第 8 位 1，把它当 +1 累进前缀差：diff 从 0 变成 1。下一步看这个 diff 以前见过没。
- 22diff=1 以前出现过（最早在下标 0）！说明下标 1…8 这段（绿色）0 和 1 一样多，长 8。没超过当前最长 8，保持。
- 23读第 9 位 1，把它当 +1 累进前缀差：diff 从 1 变成 2。下一步看这个 diff 以前见过没。
- 24diff=2 以前出现过（最早在下标 1）！说明下标 2…9 这段（绿色）0 和 1 一样多，长 8。没超过当前最长 8，保持。
- 25扫完全程，最长的平衡段是绿色这 8 个（下标 0…7，0 和 1 各 4 个），答案 8。靠「同一个 diff 再现」一遍扫描就找到了。
⚠️ 容易写错的地方
✗ 错：哈希里存 diff 每次出现的下标
✓ 对：只存第一次出现的下标
要最长段，必须配最早的同值前缀
✗ 错：忘了预置 first[0] = −1
✓ 对：必须先放 {0: −1}
否则从开头就平衡的段会被漏掉（如 [0,1]）
✗ 错：把 0 当 0 累加
✓ 对：0 要当 −1
只有 0→−1 才能让「等量」对应「和为 0 / 前缀和相等」
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
first = {0: -1}
diff = 0
best = 0
for i, x in enumerate(nums):
diff += 1 if x == 1 else -1
if diff in first:
best = max(best, i - first[diff])
else:
first[diff] = i
return bestC++
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int,int> first;
first[0] = -1;
int diff = 0, best = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
diff += nums[i] == 1 ? 1 : -1;
if (first.count(diff)) best = max(best, i - first[diff]);
else first[diff] = i;
}
return best;
}
};Java
import java.util.*;
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer,Integer> first = new HashMap<>();
first.put(0, -1);
int diff = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
diff += nums[i] == 1 ? 1 : -1;
if (first.containsKey(diff)) best = Math.max(best, i - first.get(diff));
else first.put(diff, i);
}
return best;
}
}复杂度
时间
O(n)
一遍扫描，哈希查/插 O(1)
空间
O(n)
哈希表最多存 n 个不同的 diff
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 连续数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这套「前缀和 + 哈希存最早下标」还能解哪些题？+
一大类「最长子数组满足某和性质」的题：和为 k 的最长子数组、和能被 k 整除的最长/计数（LC974/523）等。套路都是把条件转成「前缀和相等 / 同余」，用哈希记最早位置或计数。
如果问的是“数量”而不是“最长长度”呢？+
那就把哈希从「diff→最早下标」改成「diff→出现次数」，每遇到一个 diff 就把它已出现的次数累加进答案（每对相等前缀和贡献一个合法子数组）。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 连续数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。