LeetCode 525: Contiguous Array (Prefix Balance + Earliest Index Hashing)
LeetCode 525Prefix SumHash TableArrayToday we solve LeetCode 525 - Contiguous Array.
Source: https://leetcode.com/problems/contiguous-array/
English
Problem Summary
Given a binary array nums, return the maximum length of a contiguous subarray with equal number of 0 and 1.
Key Insight
Treat 0 as -1 and 1 as +1. Then the problem becomes: find the longest subarray with sum 0. If two prefix balances are equal at indices i and j, then subarray (i+1..j) has net balance zero.
Brute Force and Limitations
Checking all subarrays and counting zeros/ones each time is O(n^2) (or worse without incremental counts), which is too slow for large inputs.
Optimal Algorithm Steps
1) Initialize balance = 0, answer ans = 0, and map firstIndex.
2) Put firstIndex[0] = -1 (virtual prefix before array starts).
3) Scan array: +1 for 1, -1 for 0.
4) If balance seen before at index k, update ans = max(ans, i - k).
5) If not seen, record current index as the earliest one for this balance.
Complexity Analysis
Time: O(n).
Space: O(n) for the hash map.
Common Pitfalls
- Forgetting the base case balance 0 at index -1.
- Updating the map every time (must keep earliest index only).
- Mixing up the transform rule (0 -> -1, 1 -> +1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int findMaxLength(int[] nums) {
java.util.Map<Integer, Integer> firstIndex = new java.util.HashMap<>();
firstIndex.put(0, -1);
int balance = 0;
int ans = 0;
for (int i = 0; i < nums.length; i++) {
balance += (nums[i] == 1 ? 1 : -1);
if (firstIndex.containsKey(balance)) {
ans = Math.max(ans, i - firstIndex.get(balance));
} else {
firstIndex.put(balance, i);
}
}
return ans;
}
}func findMaxLength(nums []int) int {
firstIndex := map[int]int{0: -1}
balance, ans := 0, 0
for i, v := range nums {
if v == 1 {
balance++
} else {
balance--
}
if idx, ok := firstIndex[balance]; ok {
if i-idx > ans {
ans = i - idx
}
} else {
firstIndex[balance] = i
}
}
return ans
}class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> firstIndex;
firstIndex[0] = -1;
int balance = 0, ans = 0;
for (int i = 0; i < (int)nums.size(); i++) {
balance += (nums[i] == 1 ? 1 : -1);
if (firstIndex.count(balance)) {
ans = max(ans, i - firstIndex[balance]);
} else {
firstIndex[balance] = i;
}
}
return ans;
}
};class Solution:
def findMaxLength(self, nums: list[int]) -> int:
first_index = {0: -1}
balance = 0
ans = 0
for i, v in enumerate(nums):
balance += 1 if v == 1 else -1
if balance in first_index:
ans = max(ans, i - first_index[balance])
else:
first_index[balance] = i
return ansvar findMaxLength = function(nums) {
const firstIndex = new Map();
firstIndex.set(0, -1);
let balance = 0;
let ans = 0;
for (let i = 0; i < nums.length; i++) {
balance += nums[i] === 1 ? 1 : -1;
if (firstIndex.has(balance)) {
ans = Math.max(ans, i - firstIndex.get(balance));
} else {
firstIndex.set(balance, i);
}
}
return ans;
};中文
题目概述
给定二进制数组 nums，返回 0 和 1 数量相同的最长连续子数组长度。
核心思路
把 0 看成 -1，1 看成 +1。问题就转化为“最长和为 0 的子数组”。如果前缀平衡值在 i 和 j 两个位置相同，那么区间 (i+1..j) 的净和就是 0。
暴力解法与不足
暴力枚举所有子数组并统计 0/1 数量，时间复杂度至少 O(n^2)，数据稍大就会超时。
最优算法步骤
1）初始化 balance = 0、答案 ans = 0，以及哈希表 firstIndex。
2）先放入 firstIndex[0] = -1，表示数组起点前的虚拟前缀。
3）遍历数组：遇到 1 令平衡值 +1，遇到 0 令平衡值 -1。
4）若当前平衡值之前出现过，说明中间区间和为 0，更新最大长度。
5）若没出现过，记录该平衡值的最早位置。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（哈希表存前缀平衡值最早下标）。
常见陷阱
- 忘记初始化 firstIndex[0] = -1。
- 对同一个平衡值反复覆盖下标（应保留最早位置）。
- 把映射写反（正确是 0 -> -1、1 -> +1）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int findMaxLength(int[] nums) {
java.util.Map<Integer, Integer> firstIndex = new java.util.HashMap<>();
firstIndex.put(0, -1);
int balance = 0;
int ans = 0;
for (int i = 0; i < nums.length; i++) {
balance += (nums[i] == 1 ? 1 : -1);
if (firstIndex.containsKey(balance)) {
ans = Math.max(ans, i - firstIndex.get(balance));
} else {
firstIndex.put(balance, i);
}
}
return ans;
}
}func findMaxLength(nums []int) int {
firstIndex := map[int]int{0: -1}
balance, ans := 0, 0
for i, v := range nums {
if v == 1 {
balance++
} else {
balance--
}
if idx, ok := firstIndex[balance]; ok {
if i-idx > ans {
ans = i - idx
}
} else {
firstIndex[balance] = i
}
}
return ans
}class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> firstIndex;
firstIndex[0] = -1;
int balance = 0, ans = 0;
for (int i = 0; i < (int)nums.size(); i++) {
balance += (nums[i] == 1 ? 1 : -1);
if (firstIndex.count(balance)) {
ans = max(ans, i - firstIndex[balance]);
} else {
firstIndex[balance] = i;
}
}
return ans;
}
};class Solution:
def findMaxLength(self, nums: list[int]) -> int:
first_index = {0: -1}
balance = 0
ans = 0
for i, v in enumerate(nums):
balance += 1 if v == 1 else -1
if balance in first_index:
ans = max(ans, i - first_index[balance])
else:
first_index[balance] = i
return ansvar findMaxLength = function(nums) {
const firstIndex = new Map();
firstIndex.set(0, -1);
let balance = 0;
let ans = 0;
for (let i = 0; i < nums.length; i++) {
balance += nums[i] === 1 ? 1 : -1;
if (firstIndex.has(balance)) {
ans = Math.max(ans, i - firstIndex.get(balance));
} else {
firstIndex.set(balance, i);
}
}
return ans;
};
Comments