leetcode_525_连续数组

连续数组

描述

中等

给定一个二进制数组 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

解题

遍历数组时，有一个计数器，碰到1则加1，碰到0则减1

• 当计数器的数据为0时，说明该计数器所经过的0和1的数量是相等的
• 如果某一位置的计数器计数为x，之后又有一位置的计数器计数为x，那么这两个位置之间的0和1的数量时相等的

因此，使用哈希map记录下计数器的计数和当前的位置

并且需要找最长的序列，希望左边的位置尽可能的靠左，所以不需要更新map中已有的数据

# python
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        # 记录初始计数器计数和位置
        dic = {0: -1}
        counter = res = 0
        for i, n in enumerate(nums):
            if n == 1:
                counter += 1
            else:
                counter -= 1
            # 如果当前计数器数据已经出现在字典中，说明又一位置上的计数器为x
            # 这两个位置之间的0和1的数量是相等的
            if counter in dic:
                # 更新最长的子序列
                res = max(res, i - dic[counter])
            else:
                dic[counter] = i
            
        return res

// java
class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int counter = 0;
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1) counter++;
            else counter--;
            
            if (map.containsKey(counter)){
                res = Math.max(res, i - map.get(counter));
            }else{
                map.put(counter, i);
            }
        }
        return res;
    }
}