525.连续数组

题目描述：

解：

题目要求0和1数量相同的最长子数组，假如将0看做-1，那就是和为0的最长子数组。
那么依然是先做前缀和处理。然后通过哈希表记录某个前缀和出现的最小下标(以求最大子数组)

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n+1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + (nums[i-1] == 0 ? -1 : nums[i-1]); //前缀和处理
        }
        int ret = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0,0);
        for(int i = 2; i <= n; i++) {
            if(!map.containsKey(sum[i-2])) {
                map.put(sum[i-2], i-2); //记录最左端点
            }
            if(map.containsKey(sum[i])) {
                ret = Math.max(ret, i-map.get(sum[i]));
            }
        }
        return ret;
    }
}