leetcode 525. 连续数组（优质解法）

代码：

class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        hashMap.put(0,-1);

        int max_length=0;
        int last=0; //上一个下标的前缀和
        int now=0;  //当前下标的前缀和
        for(int i=0;i<nums.length;i++){
            int num=nums[i]==0?-1:1;    //获取当前的数据，0要视为-1
            now=last+num;
            int j=hashMap.getOrDefault(now,-2); 
            if(j!=-2){
                max_length=Math.max(max_length,i-j);
            }else{
                hashMap.put(now,i);
            }
            last=now;
        }

        return max_length;
    }
}

题解：

? ? ? ? 本题我们要找到有相同数量 0 和 1 的最长子数组，要是直接按原题这种数据来解题的话是比较困难的，对于该题我们应该换一个思路，把 0 视为 -1，那么我们要找的就是有相同数量 -1?和 1 的最长子数组，那么子数组的和就为 0 ， 我们要找的就是和为 0 的最长子数组

? ? ? ? 对于找子数组的题通常使用滑动窗口和前缀和，一般数组中具有单调性就使用滑动窗口，涉及到子数组的和就使用前缀和，很显然本题可以通过前缀和来解决

? ? ? ? 为了方便分析，我画了如下的图：

? ? ? ? sum 是前缀和数组，记录对应下标的前缀和。要寻找以 i 为尾，符合条件的子数组，加上在 0 ~ i -1 区间找到了下标 j ，j +1 - i 的子数组是符合条件的，那么 x = 0 ，并且 x= sum[ i ] - sum[ j ] ，推得：sum[ i ] = sum[ j ] ,所以要想获得 j 下标，就要判断 i 下标之前有多少下标的前缀和等于 sum[ i ]?

? ? ? ? 可以将 i 下标之前下标的前缀和存放到哈希表中，由于本题要获取的是最长子数组，所以在哈希表中以下标的前缀和为 key ，下标为 value，可以通过 j 下标与 i 下标的距离得到符合条件的子数组的长度

? ? ? ? 将前缀和以及下标存储到哈希表中时可能会出现冲突，我们要考虑如何解决，当不同的下标对应相同的前缀和时，应该存储较小的下标，因为较小的下标离 i 下标较远，得到的子数组长度更长

? ? ? ? 在使用 前缀和+哈希表 的解题方法时，哈希表一般都需要先填入一个初始数据，我们通过示例 1 来进行分析，nums=[ 0,1 ]

? ? ? ? i 下标一开始指向 0 ，当数据是 0 时视为 -1，所以此时的前缀和为 -1，要在哈希表中找的 key 值就是 -1，哈希表中没有，于是准备遍历下一个数据，在遍历之前先将当前下标的前缀和以及下标填入哈希表，

0? ? ? ? 1? ? ? ? hash

i????????????????????????

? ? ? ? i 此时指向 1 ，前缀和为 0 ，所以在哈希表中找的 key 值就是 0，哈希表中没有，但是我们知道以当前位置为末尾是有符合条件的子数组的，就是 0，1，通过上面画的图知道，子数组的长度为 i - j ，此时符合条件的子数组长度为 2 ，i 为 1，所以 j 为 -1，所以我们要在哈希表在填入的初始数据为 （0，-1）

0? ? ? ? 1? ? ? ? hash

? ? ? ? ? ?i? ? ? ? ? ? -1，0

? ? ? ? 上述便是本题的核心思想