0525. 连续数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 哈希表

1. 📝 题目描述

• leetcode

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

---

示例 1：

输入：nums = [0,1]
输出：2
说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

输入：nums = [0,1,0]
输出：2
说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

示例 3：

输入：nums = [0,1,1,1,1,1,0,0,0]
输出：6
解释：[1,1,1,0,0,0] 是具有相同数量 0 和 1 的最长连续子数组。

---

提示：

• 1 <= nums.length <= 10^5
• nums[i] 不是 0 就是 1

2. 🎯 s.1 - 前缀和 + 哈希表

c

#define OFFSET 50001
int findMaxLength(int* nums, int numsSize) {
    int* first = (int*)malloc(sizeof(int) * (2 * numsSize + 2));
    for (int i = 0; i < 2 * numsSize + 2; i++) first[i] = -2;
    first[0 + OFFSET] = -1;
    int count = 0, res = 0;
    for (int i = 0; i < numsSize; i++) {
        count += nums[i] == 1 ? 1 : -1;
        int idx = count + OFFSET;
        if (first[idx] != -2) {
            if (i - first[idx] > res) res = i - first[idx];
        } else {
            first[idx] = i;
        }
    }
    free(first);
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function (nums) {
  const map = new Map([[0, -1]])
  let count = 0,
    res = 0
  for (let i = 0; i < nums.length; i++) {
    count += nums[i] === 1 ? 1 : -1
    if (map.has(count)) res = Math.max(res, i - map.get(count))
    else map.set(count, i)
  }
  return res
}

py

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        prefix = {0: -1}
        count = res = 0
        for i, num in enumerate(nums):
            count += 1 if num == 1 else -1
            if count in prefix:
                res = max(res, i - prefix[count])
            else:
                prefix[count] = i
        return res

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 将 0 视为 -1，维护前缀和 count
• 哈希表记录每个前缀和第一次出现的位置
• 若相同前缀和再次出现，则两位置间 0 和 1 的个数相等