【LeetCode】这么简单的题，豆编又不会！
题目信息
525 - 连续数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 【 Tips 】 1 <= nums.length <= 10^5 nums[i] 不是 0 就是 1 ================================================= 输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。 ================================================= 输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 ================================================= 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contiguous-array/
菜编思路
这个不难，这几天的题都是一样的类型，前缀数组和加上哈希表的套路。
- 这里可以做一次转化，把数组中的 0 换成 -1 去做处理，这样一个含有相同数量的 0 和 1 的连续数组的和就是 0
- 当连续数组和为 0 时，加上这个连续数组的前缀数组，和不加上这个连续数组的前缀数组，他们两个的和都是一样的。
- 我们记录前缀数组之和第一次出现的位置，然后再次遇到相同和时，求两次位置的差值
参考代码
public int findMaxLength(int[] nums) { int len = nums.length; if (len < 2) return 0; Map<Integer, Integer> map = new HashMap<>(); // 位置 0 之前的前缀数组之和记做0，位置记做-1 map.put(0, -1); // 前缀数组之和 int sum = 0; // 记录最大的数组 int max = 0; for (int i = 0; i < len; i++) { if (nums[i] == 1) { sum += 1; } else { sum += -1; } if (map.containsKey(sum)) { if (i - map.get(sum) > max) max = i - map.get(sum); } else { map.put(sum, i); } } return max; }
这段代码理解起来很容易，思路很清晰，能看明白就好，今天的文章到此为止……
优雅升级
本来以为这样就结束了，豆编兴高采烈的提交完代码以后，发现运行速度处于下游水平，运行速度比最快的慢了近 5 倍……
这不行啊，然后就分析了一波上上上游水平的代码什么样子的。
public int findMaxLength(int[] nums) { // 数组长度 int len = nums.length; // 定义一个长度时nums两倍的数组，存放前缀和对应的位置 int[] sums = new int[2 * len + 1]; // 最大的数组长度 int max = 0; // 前缀数组的和 int sum = 0; for (int i = 0; i < len; ++i) { // 计算前缀数组的和，0 替换成 -1处理 sum += nums[i] == 0 ? -1 : 1; // 当sum为0时，表示这是个从头开始的数组，一定是当前最长的 if (sum == 0) max = i + 1; // 位置数组的默认位置为0，当不是0时，这个和在之前出现过 else if (sums[sum + len] != 0) max = Math.max(max, i - sums[sum + len] + 1); else // +1操作是为了避免位置为 0 时，sums数组存放 0，跟默认值冲突 sums[sum + len] = i + 1; } return max; }
这是一个空间换时间的算法，大体上还是一样的思想，只是细节上有些不一样。
这个解法有意思啊，这个两倍数组实现了哈希表的作用，存放位置信息，前缀和最小为 nums 长度的负值，这里不会出现数组越界。
前缀和为 0 时，出现的数组一定是当前最长的，避免了其他判断。
这里有一点容易出错的地方，就是i 为 0 时，直接存放数组中，会跟默认值冲突，导致 else if 的判断失效，拿不到 0 位置上的前缀数组和。
最重要的是看懂了以后，要去自己实现一遍
