知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 连续数组 ## 题目(LeetCode 525) 给定一个二进制数组 nums,找到含有相同数量 0 和 1 的最长连续子数组的长度。 ``` 输入:[0,1,0] → 输出:2([0,1]) 输入:[0,1,0,1,1] → 输出:4([0,1,0,1]) ``` ## 大白话理解 把 0 变成 -1,问题就变成了"找和为 0 的最长子数组"。 ``` 原数组:[0, 1, 0, 1, 1] 变换后:[-1, 1, -1, 1, 1] 和为 0 的子数组 → 原数组中 0 和 1 个数相等的子数组 ``` 和为 0 → prefix[j] - prefix[i] = 0 → prefix[j] = prefix[i] 用 HashMap 记录每个前缀和第一次出现的位置,再次出现时算长度。 ## 代码 ```java public int findMaxLength(int[] nums) { Map<Integer, Integer> firstIndex = new HashMap<>(); firstIndex.put(0, -1); // 前缀和 0 在 index=-1 处出现 int sum = 0, maxLen = 0; for (int i = 0; i < nums.length; i++) { sum += (nums[i] == 0) ? -1 : 1; if (firstIndex.containsKey(sum)) { maxLen = Math.max(maxLen, i - firstIndex.get(sum)); } else { firstIndex.put(sum, i); // 只记录第一次出现的位置(要最长) } } return maxLen; } ``` > 💬 **Q:这里也举例说明** > > 用 `nums = [0, 1, 0, 1]` 走一遍。把 0 看成 -1 后,"0 和 1 个数相等"就变成"子数组和为 0",即"两个位置的前缀和相同"。 > > ``` > 原数组: [0, 1, 0, 1] > 转换后: [-1, 1, -1, 1] > > 初始状态:firstIndex = {0: -1},sum = 0,maxLen = 0 > > i=0, num=0 → sum = 0 + (-1) = -1 > map 里没有 -1 → 记录 firstIndex = {0:-1, -1:0} > > i=1, num=1 → sum = -1 + 1 = 0 > map 里有 0,首次出现在 index=-1 > maxLen = max(0, 1-(-1)) = 2 > ↑ 子数组 [0,1],1 个 0 和 1 个 1 ✓ > > i=2, num=0 → sum = 0 + (-1) = -1 > map 里有 -1,首次出现在 index=0 > maxLen = max(2, 2-0) = 2 > ↑ 子数组 [1,0],1 个 0 和 1 个 1 ✓ > > i=3, num=1 → sum = -1 + 1 = 0 > map 里有 0,首次出现在 index=-1 > maxLen = max(2, 3-(-1)) = 4 > ↑ 子数组 [0,1,0,1],2 个 0 和 2 个 1 ✓ > > 结果:maxLen = 4 > ``` > > 三个要点: > - "前缀和相同"意味着这段区间里 +1 和 -1 互相抵消了,即 0 和 1 个数相等 > - `put(0, -1)` 的作用:当 sum 回到 0 时,从数组开头到当前位置整段都满足条件,长度 = `i - (-1) = i + 1` > - 只记录第一次出现的位置:同一个前缀和出现越早,`i - firstIndex` 越大,子数组越长 ### 为什么只记录第一次出现的位置? 因为要最长子数组。同一个前缀和,第一次出现的位置越靠前,子数组越长。 ## 复杂度 - 时间:O(n) - 空间:O(n) ## 一句话总结 0 变 -1,转化为"和为 0 的最长子数组"。HashMap 记录前缀和第一次出现的位置。 --- 上一篇:[02 - 和为K的子数组](./02-subarray-sum-k.md) | 下一篇:[04 - 除自身以外数组的乘积](./04-product-except-self.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入