题目
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
var findMaxLength = function(nums) {
// TODO
};
思路
// 前缀和+哈希表
// 由于「0 和 1 的数量相同」等价于「1 的数量减去 0 的数量等于 0」，我们可以将数组中的 0 视作 −1，则原问题转换成「求最长的连续子数组，其元素和为 0」。// 由于哈希表存储的是 counter 的每个取值第一次出现的下标，因此当遇到重复的前缀和时，根据当前下标和哈希表中存储的下标计算得到的子数组长度是以当前下标结尾的子数组中满足有相同数量的 0 和 1 的最长子数组的长度。遍历结束时，即可得到 nums 中的有相同数量的 0 和 1 的最长子数组的长度。
参考答案
var findMaxLength = function (nums) {
let maxLength = 0
const map = new Map()
let counter = 0 ////存储newNums的前缀和即可
map.set(counter, -1) //合为key，索引为value,初始化索引为-1，和为0
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 1) {
counter++
} else {
counter--
}
if (map.has(counter)) {
maxLength = Math.max(maxLength, i - map.get(counter))
} else {
map.set(counter, i)
}
}
return maxLength
}
const arr1 = [0, 1]
const arr2 = [0, 1, 0, 1]
console.log(findMaxLength(arr1))
console.log(findMaxLength(arr2))
