题目链接
题目:
分析:
- 如果我们直接做这道题, 有点麻烦
- 如果我们将所有的0都变成1, 那么找到数量相同的0和1的最长连续子数组, 就是找最长连续子数组的和为0, 那么就和之前的题目<找到和为k的子数组>有点像, 需要用前缀和+哈希表来完成
- 在[0,i-1]区间找到前缀和= sum[i] - 0, 即sum[i]
- 那么哈希表中, 我们要存的就不是前缀和 和 个数了, 而应该存的是 前缀和sum 和 此时的下标i
- 什么时候将前缀和存在哈希表中? 使用完之后, 即更新完结果之后
- 如果有重复的sum 和i , 只保留原哈希表中存的i, 无需更新, 因为题目中要的是最长的子数组, 先存进去的下标一定是更靠前的, 子数组更长
- 默认前缀和为0的情况, 即[0,i] 的和为0, 那么我们应该在-1的位置找前缀和, 所以要添加(0,-1)
- 题目中要返回数组的长度, 长度应该怎么算呢?
代码:
class Solution {public int findMaxLength(int[] nums) {Map<Integer, Integer> hash = new HashMap<>();hash.put(0, -1);int sum = 0;//前缀和int ret = 0;// 最长的长度for (int i = 0; i < nums.length; i++) {sum += (nums[i] == 0 ? -1 : 1);//无需真的将数组中的0改成1, 只需在此判断即可if (hash.containsKey(sum)) {ret = Math.max(ret, i - hash.get(sum));} else {hash.put(sum, i);}}return ret;}
}
