题目大意：
连续数组
给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1:
输入: [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:
输入: [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
注意: 给定的二进制数组的长度不会超过50000。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=525
解题思路分析：
我们之前文章说过遇到子数组问题时，多数要考虑到使用双指针（滑动窗口）的方式来解题，而本题使用双指针却很难想出合理的思路，这就轮到解决子数组问题的另一高手「前缀和」来大显身手了。这和我们之前讲过的 LEETCODE 1371. Find the Longest Substring Containing Vowels in Even Counts 解题思路分析 这篇文章的思路非常相似，可以作为参考。
回到本题的解题思路上，我们需要遍历一遍数组，来计算数组的前缀和，为了方便计算，我们将数组中的0全部变为-1，这样当前缀和为0时，说明这一段区间内1和0（-1）的数量一致，这是一个合理区间，我们用该区间长度去更新最大长度即可。（重点来了）另外，我们需要定义一个HashMap，key是当前前缀和，value是首次出现该前缀和的下标。当该前缀和首次出现时，我们将该和以及当前下标存入map，反之如果map中存在当前前缀和，那么当前位置到该前缀和首次出现位置之间的区间即是一个合理区间。比如位置0到4的前缀和3，而0到8的前缀和也是3，那么说明5到8之间的和一定是0（1和-1的数量一样）。同样我们需要用该区间长度去更新全局最大长度。循环结束后，全局最大长度即是返回结果。
实现代码：
public int findMaxLength(int[] nums) {
Map<Integer, Integer> map=new HashMap<>();
int preSum=0; // 前缀和
int maxLength=0; // 最长区间
for(int i=0;i<nums.length;i++){
if(nums[i]==1) preSum+=1;
else preSum+=-1; // 为了计算方便，使用-1代替0
// 如果前缀和是0，当前前缀区间即是一个合理解，更新全局最大长度
if(preSum==0) maxLength=Math.max(maxLength,i+1);
else{
// 如果当前前缀和出现过
if(map.containsKey(preSum)){
// 当前前缀和首次出现位置与当前位置间的区间为一个合理解
maxLength=Math.max(maxLength,i-map.get(preSum));
}else{ // 如果当前前缀和没有出现过
map.put(preSum,i); // 将当前区间和以及下标计入map
}
}
}
return maxLength;
}本题解法执行时间为21ms。
Runtime: 21 ms, faster than 37.77% of Java online submissions for Contiguous Array.
Memory Usage: 49.1 MB, less than 100.00% of Java online submissions for Contiguous Array.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-525-contiguous-array-解题思路分析/