难度: Medium
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1：
输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2：
输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
提示：
1 <= nums.length <= 105nums[i] 不是 0 就是 1注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/
运行时间: 107 ms
内存: 23.7 MB
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
cur = 0
dic = {}
for i in range(len(nums)):
cur += 1 if nums[i] else -1
if cur not in dic:
dic[cur] = [i, i]
else:
dic[cur][1] = i
res = 0
for i in dic.values():
res = max(res, i[1] - i[0])
if 0 in dic:
res = max(res, dic[0][1] + 1)
return res
该题解采用了哈希表记录前缀和的方法。定义cur为当前前缀和，遍历数组nums时，遇到1则cur加1，遇到0则cur减1。用一个字典dic记录cur第一次出现的位置和最后一次出现的位置。最后，遍历dic中的所有值，计算最大的位置差值，即为含有相同数量的0和1的最长连续子数组的长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
cur = 0 # 当前前缀和
dic = {} # 字典，用于记录前缀和的位置信息
for i in range(len(nums)):
cur += 1 if nums[i] else -1 # 遇到1则加1，遇到0则减1
if cur not in dic:
dic[cur] = [i, i] # 记录cur第一次出现的位置
else:
dic[cur][1] = i # 更新cur最后一次出现的位置
res = 0 # 最长连续子数组的长度
for i in dic.values():
res = max(res, i[1] - i[0]) # 计算位置差值
if 0 in dic:
res = max(res, dic[0][1] + 1) # 如果存在前缀和为0的情况，需要特殊处理
return res
使用前缀和来表示0和1的数量关系是一种有效的方法来检测子数组中0和1的数量是否相等。在这种方法中，每遇到1，前缀和增加1；每遇到0，前缀和减少1。这样，如果在两个不同位置的前缀和相同，意味着这两个位置之间的子数组中0和1的数量正好抵消，即数量相等。这种方法利用了数学中的差分原理，是解决这类问题的一种高效技术。
是的，这种方法确保了计算的子数组中0和1的数量相等。当我们记录下一个前缀和首次和最后一次出现的位置时，其实是在找到所有相同前缀和的区间。若两个位置的前缀和相同，那么这两个位置之间的区间（不包括第一个位置）的前缀和的变化量为零，即这个区间内0和1的数量相等。因此，通过计算这两个位置的差值，我们可以得到一个0和1数量相等的子数组的长度。
前缀和为0的特殊处理是因为当前缀和为0时，它表示从数组开始到当前位置的全部元素构成的子数组0和1的数量完全相等。dic[0][1]是前缀和为0最后一次出现的位置，即从索引0到dic[0][1]的子数组是平衡的。因为数组索引从0开始计数，所以要加1来正确计算这个子数组的长度（包括起始点）。例如，如果前缀和为0最后一次出现在索引5，那么从索引0到索引5的子数组长度为6，这就是为什么要加1的原因。