LeetCode 525. 连续数组

约 4 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 需复习 10-20 腾讯 字节 拼多多
标签
数组 哈希表 前缀和

题目描述

✅ 525. 连续数组

image-20260928221047128

题意分析

数组只包含 0 和 1，要求返回两者数量相同的最长连续子数组的长度。把每个 0 的贡献记为 -1、每个 1 的贡献记为 +1，区间和就是其中 1 的数量减去 0 的数量，因此目标变成最长的和为 0 的连续区间。

解法：前缀和 + 最早位置哈希表

核心思路

[!blue]

遍历到下标 i 时，balance 表示 nums[0..i] 中 1 与 0 的数量差。如果下标 j 处的前缀也有相同的数量差，两段前缀相减后，区间 nums[j+1..i] 的数量差就是 0，长度为 i-j。反过来，任何合法区间的左端之前与右端处，前缀状态也必然相同。

用 first 记录每种 balance 第一次出现的下标。固定右端点 i 后，左侧相同状态出现得越早，区间越长；更晚的位置不可能带来更优答案，所以已有记录不能覆盖。依次考察每个右端点并取最大长度，就不会漏掉全局最优区间。

数组之前的空前缀数量差为 0，位置记作 -1，因此先存入 first[0] = -1。这样当前缀本身就平衡时，仍可统一用 i-(-1) 得到长度，不需要单独处理从下标 0 开始的区间。

解题步骤

  1. 初始化 balance = 0、最长长度 ans = 0，建立哈希表并写入 first[0] = -1。
  2. 从左到右遍历：遇到 1 令 balance++，遇到 0 令 balance--。
  3. 若当前状态已出现，用 i-first[balance] 更新 ans；否则写入 first[balance] = i，为后续右端点保留候选。
  4. 遍历结束返回 ans。只有一个元素或所有元素相同时，状态不会重复，答案保持为 0。

代码实现

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> first = new HashMap<>();

        // 数组之前的空前缀让从下标零开始的平衡区间也能计入。
        first.put(0, -1);

        int balance = 0;
        int ans = 0;

        for (int i = 0; i < nums.length; i++) {
            balance += nums[i] == 1 ? 1 : -1;
            Integer index = first.get(balance);

            if (index != null) {
                ans = Math.max(ans, i - index);
            } else {
                // 首次出现才记录，更早的位置为后续保留更长候选。
                first.put(balance, i);
            }
        }

        return ans;
    }
}

func findMaxLength(nums []int) int {
    // 数组之前的空前缀让从下标零开始的平衡区间也能计入。
    first := map[int]int{0: -1}
    balance, ans := 0, 0

    for i, num := range nums {
        if num == 1 {
            balance++
        } else {
            balance--
        }

        if index, ok := first[balance]; ok {
            if i-index > ans {
                ans = i - index
            }
        } else {
            // 首次出现才记录，更早的位置为后续保留更长候选。
            first[balance] = i
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。数组只遍历一次，哈希表查询和写入的均摊时间为 $O(1)$。
  • 空间复杂度：$O(n)$。最坏情况下会记录 $n + 1$ 个不同的前缀状态。

关键点总结

[!green]

  • balance 是前缀中两种元素的数量差，计算时改变贡献即可，无需修改输入数组。
  • 相同前缀状态之间恰好是一段合法区间，最早状态给出当前右端点的最长候选。
  • 空前缀也必须参与比较，0 -> -1 使从数组开头开始的区间使用同一套公式。

易错点总结

[!yellow]

  • 覆盖首次位置：会丢失最早的左侧前缀，使后续算出的区间变短。
  • 遗漏 0 -> -1：会漏掉从下标 0 开始的合法区间。
  • 长度多加 1：表中保存的是区间左端点的前一个位置，公式应为 i - index。
  • 把 0 当作 0 累加：此时前缀只统计 1 的数量，已不再表示两类元素的数量差。
  • 把 Go 的缺失键当作下标 0：必须用 index, ok 区分“没有记录”和“首次位置正好为 0”。

相似题目

题目 难度 关联与区别
560. 和为 K 的子数组 中等 把0改成-1后，0与1等量等价于区间和为0；本题保存最早前缀位置求最长长度，而非统计数量。
1124. 表现良好的最长时间段 中等 同样把两类元素映射成正负贡献，原题要求区间和严格为正，本题要求等于0。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/10044428
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！