525. 连续数组

约定不等于承诺〃 2022-10-18 11:27 139阅读 0赞

> 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
> 
>  
> 
> 示例 1:
> 
> 输入: nums = \[0,1\]  
> 输出: 2  
> 说明: \[0, 1\] 是具有相同数量 0 和 1 的最长连续子数组。  
> 示例 2:
> 
> 输入: nums = \[0,1,0\]  
> 输出: 2  
> 说明: \[0, 1\] (或 \[1, 0\]) 是具有相同数量0和1的最长连续子数组。
> 
>

class Solution {
        public int findMaxLength(int[] nums) {
            /**
            前缀和思想:
                Map <前缀和, 下标>
                    如果我们吧数组里面的0改为-1 
                        如果当前前缀和==历史前缀和,那么说明中间的子序列和是0
                        更新他的最大长度
             */
    
             Map<Integer,Integer> map=new HashMap();//<前缀和, 下标>
             for(int i=0;i<nums.length;i++){
                 if(nums[i]==0){//如果我们吧数组里面的0改为-1 
                     nums[i]=-1;
                 }
             }
    
             map.put(0,-1);
             int sum=0;
             int maxLen=0;
             for(int i=0;i<nums.length;i++){
                 sum+=nums[i];
                 if(map.containsKey(sum)){//如果当前前缀和==历史前缀和,那么说明中间的子序列和是0
                     maxLen=Math.max(maxLen,i-map.get(sum));//更新他的最大长度
                 }else{
                     //不包含就放进去
                     map.put(sum,i);
                 }
             }
             return maxLen;
    
        }
    }

**里面的put(0,-1) 是因为  因为01个数相等就是整个都符合条件，相当于左侧不需要减去,得加上**

**i-(-1)=i+1  **

**一般value是坐标的都是默认(0,-1) ,如果value是和的,那么就是(0,1);**