525. Contiguous Array

这道题很巧妙，把0换成-1来求preSum, 如果遇到曾经出现过的preSum，说明中间的subsum = 0. 也就是-1，1的个数相同，即0， 1的个数相同。注意一下map如果有key(sum), 我们不要put去更新map, 因为我们要保留最早出现的那一个preSum, 这样才好在未来算出最长的subarray which sum equals to 0.

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        //[0, 1] 
        //when i = 1, we get sum = 0, we check map contains key = 0 , so we have to put(0, -1) to get the result
        //[0,1,0,1]
        map.put(0 , -1);
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == 1){
                sum += 1;
            } else if (nums[i] == 0){
                sum += -1;
            }
            if (map.containsKey(sum)){
                res = Math.max(res, i - map.get(sum));
            } else {
                //do not update the map coz we want to get the max length
                map.put(sum, i);
            }
        }
        return res;
    }
}