LeetCode LCR 011. 连续数组

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 哈希表（推荐）
相似题目

题目描述

✅ LCR 011. 连续数组

思路分析

解法一：前缀和 + 哈希表（推荐）

核心思路：

将 0 视为 -1，1 视为 +1，求前缀和。

若两位置前缀和相同，说明区间内 0 与 1 数量相等。

使用哈希表记录前缀和首次出现的位置，更新最长长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示哈希表大小。

// 前缀和 + 哈希表
class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> firstIndex = new HashMap<>();
        firstIndex.put(0, -1);

        int sum = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 1) ? 1 : -1;
            if (firstIndex.containsKey(sum)) {
                ans = Math.max(ans, i - firstIndex.get(sum));
            } else {
                firstIndex.put(sum, i);
            }
        }

        return ans;
    }
}

// 前缀和 + 哈希表
func findMaxLength(nums []int) int {
	firstIndex := make(map[int]int)
	firstIndex[0] = -1

	sum := 0
	ans := 0
	for i, v := range nums {
		if v == 1 {
			sum++
		} else {
			sum--
		}
		if idx, ok := firstIndex[sum]; ok {
			if i-idx > ans {
				ans = i - idx
			}
		} else {
			firstIndex[sum] = i
		}
	}

	return ans
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和
523. 连续的子数组和	中等	前缀和
974. 和可被 K 整除的子数组	中等	前缀和
1248. 统计「优美子数组」	中等	前缀和
930. 和相同的二元子数组	中等	前缀和
325. 和等于 k 的最长子数组长度	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/83305033