DeepSeek LeetCode 525. 连续数组 Java实现

importjava.util.HashMap;importjava.util.Map;classSolution{publicintfindMaxLength(int[]nums){// 前缀和（把 0 当作 -1，1 当作 +1） -> 第一次出现该前缀和的下标Map<Integer,Integer>map=newHashMap<>();// 前缀和为 0 的"虚拟位置"在 -1，用于处理从头开始的子数组map.put(0,-1);intsum=0;intmaxLen=0;for(inti=0;i<nums.length;i++){// 0 视为 -1，1 视为 +1sum+=(nums[i]==1)?1:-1;if(map.containsKey(sum)){// 相同前缀和之间的区间，0 和 1 数量相等maxLen=Math.max(maxLen,i-map.get(sum));}else{// 只记录第一次出现的位置，保证区间最长map.put(sum,i);}}returnmaxLen;}}

思路：把 0 变成 -1，转成"和为 0 的最长子数组"

要让某个子数组中 0 和 1 的数量相等，可以做一个等价转换：

· 把 0 看成 -1，1 看成 +1；
· 那么"0 和 1 数量相等"就等价于"该子数组的元素之和为 0"。

于是问题转成经典的 “求和为 0 的最长连续子数组”。

设 prefix[i] = nums[0] + … + nums[i-1]（把 0 当 -1 之后的和）。
子数组 nums[j…i-1] 和为 0，即：

prefix[i] - prefix[j] = 0 ⟺ prefix[i] = prefix[j]

也就是说，两个位置的前缀和相等，它们之间的子数组就满足 0、1 数量相等。

因此：

1. 用哈希表记录每个前缀和第一次出现的下标；
2. 遍历数组，一边累加前缀和一边检查；
3. 如果当前前缀和之前出现过，用 i - firstIndex 更新最长长度；
4. 如果没出现过，记录当前下标（只记第一次，才能得到最长区间）；
5. 初始放入 {0: -1}，用于处理从下标 0 开始的子数组。

细节

· 初始 {0: -1} 必不可少：例如 [0, 1] 整体合法时，到下标 1 前缀和回到 0，用 1 - (-1) = 2 得到正确长度。
· 只记录第一次出现：同一前缀和后续再出现时，区间长度只会更短，无需覆盖。
· 返回 0：如果没有合法子数组，maxLen 保持 0。

复杂度

· 时间复杂度：O(n)，一次遍历；
· 空间复杂度：O(n)，哈希表最多存储 n + 1 个不同前缀和。