连续数组

怎样从“nums 含 0/1,最长连续子数组 0/1 个数相等。”推导出 前缀和 · 连续数组，并证明每次状态变化都不会漏掉答案？

中心结论：前缀和 count0-count1;map 最早出现某和→最长。

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

在本站主例中，nums 含 0/1,最长连续子数组 0/1 个数相等。

算法最终需要得到或观察：最长长度 6(0..5)。

每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“前缀累计仪”，明确答案需要观察什么。
2. 2状态只维护 prefix diff、map 最早下标。
3. 3转移每一步按照 前缀和 count0-count1;map 最早出现某和→最长。
4. 4收尾读取 最长长度 6(0..5)。，并复核边界与复杂度。

把“某段区间”改写成“两个前缀之间的关系”。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：prefix diff、map 最早下标。

0 和 1 的数量相同可以转化为两者数量相差为 0，如果将 0 看作为 -1，那么原题转化为求最长连续子数组，其元素和为 0 。又变成了区间内求和的问题，自然而然转换为前缀和来处理。假设连续子数组是 [i,j] 区间，这个区间内元素和为 0 意味着 prefixSum[j] - prefixSum[i] = 0，也就是 prefixSum[i] = prefixSum[j]。不断累加前缀和，将每个前缀和存入 map 中。一旦某个 key 存在了，代表之前某个下标的前缀和和当前下标构成的区间，这段区间内的元素和为 0 。这个区间是所求。扫完整个数组，扫描过程中动态更新最大区间长度，扫描完成便可得到最大区间长度，即最长连续子数组。

前缀和 count0-count1;map 最早出现某和→最长。

执行过程中持续维护：prefix diff、map 最早下标。

正确性依赖以下不变量：diff 相同则中间段 0/1 平衡。

面试时可以压缩为：前缀和+哈希 O(n)。

落到当前题，执行机制可以压缩为：前缀和 count0-count1;map 最早出现某和→最长。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums 含 0/1,最长连续子数组 0/1 个数相等。 因为：前缀和 count0-count1;map 最早出现某和→最长。
2. 2prefix[i] = 前 i 个元素和O(n) 建前缀和。 因为：把区间查询变 O(1)。
3. 3prefix[1] = prefix[0] + nums[0] = 0扩展前缀表。 因为：定义式累加。
4. 4prefix[2] = prefix[1] + nums[1] = 1扩展前缀表。 因为：定义式累加。
5. 5prefix[3] = prefix[2] + nums[2] = 1扩展前缀表。 因为：定义式累加。
6. 6sum(0,2) = 1区间查询完成。 因为：前缀和标准应用。
7. 7prefix[i] = 前 i 个元素和O(n) 建前缀和。 因为：把区间查询变 O(1)。
8. 8收尾与复杂度最长长度 6(0..5)。 因为：时间 O(n) · 空间 O(1)。前缀和 count0-count1;map 最早出现某和→最长。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func findMaxLength(nums []int) int {
	dict := map[int]int{}
	dict[0] = -1
	count, res := 0, 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			count--
		} else {
			count++
		}
		if idx, ok := dict[count]; ok {
			res = max(res, i-idx)
		} else {
			dict[count] = i
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="prefix-sum-range", nums=[0,1,0]
    //    期望：最长长度 6(0..5)。
    //
    // 2. 失败 / 未命中
    //    检查：把 0 变 -1 可化成和为 0 最长。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC560 和为 K；LC974 整除 K
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums 含 0/1,最长连续子数组 0/1 个数相等。
2. 2重复每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。
3. 3优化前缀和 count0-count1;map 最早出现某和→最长。
4. 4证明diff 相同则中间段 0/1 平衡。
5. 5复杂度时间 O(n)，空间 O(1)