题目：

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

 示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
 

提示：

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1

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

解题思路：

哈希表+HashMap：@[小虎]

1.规则是：遇到数字0，和就减1，遇到数字1，和就加1；

2.创建一个哈希表map，其中key值为当前的cur值，value为当前位置索引index；

3.如果哈希表中存在当前cur值，则找到其位置索引，然后在index和 index-map.get(cur)中选取最大值，即为最优解。如果哈希表中不存在当前cur，则将cur和当前位置索引加入到哈希表中。

解释：

1.为什么要在哈希表中插入{0, -1}?

计算子数组[i,j]的和==sum[j] – sum[i-1]，当子数组的和仅为第一个元素时==sum[0]-sum[0-1]=sum[0]-sum[-1]，map中key为前缀和，value为当前前缀和的下标，这时候下标为-1，前缀和没有，故为0，所以才有的{0，-1}。

2.为什么在哈希表中找到了相同的 curcur 值则算找到了一串连续数组？

 

 java代码：

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

 python3代码：

 1 class Solution:
 2     def findMaxLength(self, nums: List[int]) -> int:
 3         map = {}
 4         map[0] = -1
 5         cur, ans = 0, 0
 6         for i in range(len(nums)):
 7             if nums[i] == 0:
 8                 cur -= 1
 9             else:
10                 cur += 1
11             if cur in map:
12                 ans = max(ans, i - map[cur])
13             else:
14                 map[cur] = i
15         return ans

原文地址：http://www.cnblogs.com/liu-myu/p/16807180.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性