难度: 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运行时间: 105 ms
内存: 24.4 MB
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
sumIJ=defaultdict(list)
anscnt=0
sumIJ[0].append(-1)
for idx,num in enumerate(nums):
anscnt+= -1 if num==0 else 1
sumIJ[anscnt].append(idx)
ansMaxLen=0
for sumv,ijlist in sumIJ.items():
ansMaxLen=max(ansMaxLen,ijlist[-1]-ijlist[0])
return ansMaxLen
这道题目的解法使用了一种基于前缀和和哈希表的技术。具体思路是，首先将数组中的0视为-1，这样问题转换为找出和为0的最长子数组。遍历数组时，我们维护一个累加和anscnt，每遇到1增加1，每遇到0减少1。使用一个哈希表sumIJ来记录每个累加和第一次出现的位置和最后一次出现的位置。如果在某个位置的累加和之前出现过，说明从上一次出现该累加和的位置到当前位置的子数组中0和1的数量相等。通过比较所有这样的子数组，找到最长的一个。
时间复杂度: O(n)
空间复杂度: O(n)
# 类定义
class Solution:
# findMaxLength函数定义
def findMaxLength(self, nums: List[int]) -> int:
# 哈希表用来存储各个累计和首次和最后一次出现的索引
sumIJ = defaultdict(list)
# 用于计算累计和
anscnt = 0
# 初始化累计和为0的情况
sumIJ[0].append(-1)
# 遍历数组，更新累计和和哈希表
for idx, num in enumerate(nums):
anscnt += -1 if num == 0 else 1
sumIJ[anscnt].append(idx)
# 初始化最大长度为0
ansMaxLen = 0
# 遍历哈希表，寻找最长的子数组长度
for sumv, ijlist in sumIJ.items():
ansMaxLen = max(ansMaxLen, ijlist[-1] - ijlist[0])
# 返回最大长度
return ansMaxLen
将0视为-1而1保持不变的转换，是为了将原问题转化为寻找和为0的最长子数组问题。这是因为，在原数组中，我们需要找到包含相同数量的0和1的子数组。通过将0视为-1，数组中的0和1相互抵消的和为0，这样就可以利用前缀和来快速判断任意子数组中0和1的数量是否相等。此转换使得问题可以通过计算累积和来简化解决，而不必对每个子数组分别计数。
在哈希表中记录累加和第一次和最后一次出现的位置，是为了能够快速找到具有相同累加和的最远距离的两个索引。如果两个不同位置的累加和相同，这意味着这两个位置之间的子数组的和为0（即0和1的数量相等）。通过记录这些位置，我们可以计算出每个具有相同累加和的最长子数组的长度，从而找到所有子数组中长度最大的那一个。
哈希表`sumIJ`在算法中起到了存储和检索累加和及其对应索引的关键角色。它允许算法在O(1)时间内查找任何累加和之前是否出现过，并快速检索该累加和的首次和最后一次出现位置。通过这种方式，算法能够有效地判断不同位置之间是否存在和为0的子数组，并计算出这些子数组的长度，以找到最长的符合条件的子数组。
这个逻辑基于前缀和的性质。前缀和是指从数组的开始到当前元素的所有元素的累加和。如果在两个不同的索引处，前缀和相同，这意味着这两个索引之间的子数组的总和为0。在本问题的上下文中，因为0被视为-1，1视为1，这样子数组的和为0意味着其中0的数量等于1的数量。因此，通过检查累加和的重复出现，我们可以找到0和1数量相等的最长子数组。