LeetCode 题解工作台
连续数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 示例 1： 输入： nums = [0,1] 输出： 2 说明： [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。 示例 2： 输入： nums = [0,1,0] 输出： 2 说…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
根据题目描述，我们可以将数组中的 视作 ，这样当遇到 时，前缀和 就会减一，当遇到 时，前缀和 就会加一。因此，假设前缀和 在下标 和 处的值相等，其中 $j < i$，那么从下标 $j + 1$ 到 的子数组中 和 的数量就是相等的。 我们使用哈希表存储所有的前缀和以及它们第一次出现的下标，初始时，我们将 的前缀和映射到 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1：
输入：nums = [0,1] 输出：2 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2：
输入：nums = [0,1,0] 输出：2 说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
示例 3：
输入：nums = [0,1,1,1,1,1,0,0,0] 输出：6 解释：[1,1,1,0,0,0] 是具有相同数量 0 和 1 的最长连续子数组。
提示：
1 <= nums.length <= 105nums[i]不是0就是1
解题思路
方法一：前缀和 + 哈希表
根据题目描述，我们可以将数组中的 视作 ，这样当遇到 时，前缀和 就会减一，当遇到 时，前缀和 就会加一。因此，假设前缀和 在下标 和 处的值相等，其中 ，那么从下标 到 的子数组中 和 的数量就是相等的。
我们使用哈希表存储所有的前缀和以及它们第一次出现的下标，初始时，我们将 的前缀和映射到 。
遍历数组，计算前缀和 ，如果 已经在哈希表中，那么我们就找到了一个和为 的子数组，其长度为 ，其中 是哈希表中保存的 第一次出现的下标。如果 不在哈希表中，我们将 与它的下标 存入哈希表。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
d = {0: -1}
ans = s = 0
for i, x in enumerate(nums):
s += 1 if x else -1
if s in d:
ans = max(ans, i - d[s])
else:
d[s] = i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is scanned once and hash map operations are O(1) on average. Space complexity is O(n) to store prefix sums in the hash map, which is necessary for efficient lookups. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
You may notice that a naive double loop approach times out for large arrays.
- question_mark
Converting 0s to -1s is a common hint that this is a prefix sum pattern.
- question_mark
Hash map usage suggests tracking first occurrences to maximize subarray length.
常见陷阱
外企场景- error
Forgetting to convert 0s to -1s, which breaks the sum-to-zero pattern.
- error
Overwriting the first occurrence of a prefix sum in the hash map, which can underestimate the maximum length.
- error
Trying to return the subarray itself instead of just its length, adding unnecessary complexity.
进阶变体
外企场景- arrow_right_alt
Count the number of contiguous subarrays with equal 0s and 1s instead of maximum length.
- arrow_right_alt
Handle arrays with more than two binary values, e.g., 0,1,2, requiring multiple prefix sums.
- arrow_right_alt
Find maximum length subarray with equal numbers of two specific elements in a non-binary array.