[LeetCode] 525. Contiguous Array

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

连续数组。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/contiguous-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题目看似简单但是这个思路比较难想到。这个题的 tag 是 hash table，感觉可以往前缀和为 0 的思路上去靠。题目问的是包含相同数量的 0 和 1 的子数组的长度，这里我们需要灵活运用前缀和这个思路。如果把 0 替换成 -1，也就把题目转化为满足条件的子数组的和会是 0，因为 -1 和 1 是成对出现的。所以做法是创建一个 hashmap 记录前缀和和他最后一次出现的位置的 index。扫描的时候就按照加前缀和的方式做，当遇到某一个前缀和 X 已经存在于 hashmap 的时候，就知道这一段区间内的子数组的和为 0 了，否则这个前缀和不可能重复出现。举个例子，比如 [0,1,0] 好了，一开始往 hashmap 存入了初始值 0 和他的下标 -1（这是大多数前缀和的题都需要做的初始化），当遍历完前两个元素 0（-1）和1之后，此时又得到这个 prefix sum = 0，此时去看一下 i - map.get(sum) 的值是否能更大，以得出这个最长的子数组的长度。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int findMaxLength(int[] nums) {
 3         int res = 0;
 4         int sum = 0;
 5         HashMap<Integer, Integer> map = new HashMap<>();
 6         map.put(0, -1);
 7         for (int i = 0; i < nums.length; i++) {
 8             sum += (nums[i] == 1 ? 1 : -1);
 9             if (map.containsKey(sum)) {
10                 res = Math.max(res, i - map.get(sum));
11             } else {
12                 map.put(sum, i);
13             }
14         }
15         return res;
16     }
17 }

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @return {number}
 4  */
 5 var findMaxLength = function(nums) {
 6     let map = new Map();
 7     map.set(0, -1);
 8     let res = 0;
 9     let sum = 0;
10     
11     for (let i = 0; i < nums.length; i++) {
12         sum += nums[i] == 0 ? -1 : 1;
13         if (map.has(sum)) {
14             res = Math.max(res, i - map.get(sum));
15         } else {
16             map.set(sum, i);
17         }
18     }
19     return res;
20 };

前缀和prefix sum题目总结

LeetCode 题目总结