https://leetcode.cn/problems/A1NYOS/
https://leetcode.cn/problems/contiguous-array/
难度：☆☆☆☆
题目：
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例：
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
方法：数组，哈希表+前缀和
和LCR 010题不同的是：
- 本题的哈希表map，键为和，值为该和第一次出现的位置。
- 0和1的数量相同，等价于1的数量减去0的数量等于0，我们可将数组中0视作-1，则原问题转换为求最长的连续子数组，其元素和为0。LCR 010求的是和为k，本题可以看做和为0，即k=0。
Python1：两次遍历
- 时间复杂度：O(n)，其中n是nums的长度。
- 空间复杂度：O(n)。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
from collections import defaultdict
# 构建前缀和
n = len(nums)
presum = [0] * (n + 1)
for idx, val in enumerate(nums):
if val == 1:
presum[idx + 1] = presum[idx] + val
else:
presum[idx + 1] = presum[idx] - 1
ret = 0
dic = defaultdict(int)
# 遍历前缀和
for idx, val in enumerate(presum):
# 如果当前前缀和出现在字典中，说明该前缀和在前面出现过，不断添加n个元素后，前缀和不变
# 说明中间的这n个元素和为0
if val in dic:
first_index = dic[val]
ret = max(ret, idx - first_index)
else:
dic[val] = idx
return ret
Python2：一次遍历
我们可以一边构建前缀和，一边遍历前缀和。
- 时间复杂度：O(n)，其中n是nums的长度。
- 空间复杂度：O(n)。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
from collections import defaultdict
dic = defaultdict(int)
ret, presum = 0, 0
# LCR 010题在这里给的是1，因为那个题哈希表的值是个数
# 本题是索引，而哈希表比数组多一位，第一个前缀和0的索引给-1
dic[0] = -1
for idx, val in enumerate(nums):
# 遍历数组，遇到1时，presum加1，遇到0时，presum减1
if val == 1:
presum += 1
else:
presum -= 1
# 如果当前前缀和出现在字典中，说明该前缀和在前面出现过，不断添加n个元素后，前缀和不变
# 说明中间的这n个元素和为0
if presum in dic:
first_index = dic[presum]
ret = max(ret, idx - first_index)
else:
dic[presum] = idx
return ret
Java1：两次遍历
- 时间复杂度：O(n)，其中n是nums的长度。
- 空间复杂度：O(n)。
class Solution {
public int findMaxLength(int[] nums) {
int maxLength = 0;
HashMap<Integer, Integer> map = new HashMap<>();
int n = nums.length;
int[] preSum = new int[n + 1];
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
preSum[i + 1] = preSum[i] + nums[i];
} else {
preSum[i + 1] = preSum[i] - 1;
}
}
for (int i = 0; i < preSum.length; i++) {
if (map.containsKey(preSum[i])) {
int firstIndex = map.get(preSum[i]);
maxLength = Math.max(maxLength, i - firstIndex);
} else {
map.put(preSum[i], i);
}
}
return maxLength;
}
}
Java2：一次遍历
- 时间复杂度：O(n)，其中n是nums的长度。
- 空间复杂度：O(n)。
class Solution {
public int findMaxLength(int[] nums) {
int maxLength = 0, preSum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
// 遍历数组，遇到1时，presum加1，遇到0时，presum减1
if (nums[i] == 1) {
preSum += 1;
} else {
preSum -= 1;
}
if (map.containsKey(preSum)) {
maxLength = Math.max(maxLength, i - map.get(preSum));
} else {
map.put(preSum, i);
}
}
return maxLength;
}
}