连续数组
Tips
题目类型: 前缀和 + HashMap
相关题目:
题目
给定一个二进制数组 nums, 找到含有相同数量的 0 和 1 的最长连续子数组, 并返回该子数组的长度.
示例
输入: nums = [0, 1, 0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的 最长连续子数组.
题解
找出 nums 中的某个连续子数组, 使得这个子数组中有相同数量的 0 和 1. 不妨把 0 看作 -1, 这就变成了找出某个子数组的和为 0.
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxLength = function (nums) {
const n = nums.length
const preSum = new Array(n + 1).fill(0)
const map = new Map([[0, 0]])
let max = 0
for (let i = 0; i < n; i++) {
// 把 0 看作 -1, 加入到前缀和中
preSum[i + 1] = preSum[i] + (nums[i] === 0 ? -1 : 1)
}
for (let i = 1; i <= n; i++) {
const sum = preSum[i]
if (map.has(sum)) {
// 当再次出现该前缀和时, 说明和前面那个前缀和之间 0 和 1 的数目相同
// 遂计算间距大小, 取最大值
max = Math.max(max, i - map.get(sum))
} else {
// 记录前缀和下标
map.set(sum, i)
}
}
return max
}