525. Contiguous Array

T: O(n)

S: O(n)

class Solution {
    public int findMaxLength(int[] nums) {

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            
            // use prefix sum, but change 0 to -1, so the target we want become 0
            if (nums[i] == 0) {
                sum += -1;
            } else {
                sum += nums[i];
            }
            if (map.containsKey(sum)) { // sum - target (target is 0)
                res = Math.max(res, i - map.get(sum));
            }
            // because ask the max length, so only when key doesn't exist, update the hashmap
            // map.putIfAbsent(sum, i);
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return res;
    }
}

/*
thought: use prefix sum, but change 0 to -1, so the target we want become 0

[0,1, 1, 1] => ans: 2
[0,0, 1, 1] => ans: 4
[0,1, 0, 1] => ans: 4
[0,1, 1, 0] => ans: 4


prefix sum - prefix sum = 0 
   0 1  2
  [1,1, 0, 1]
   1 2. 2. 3
   
   [0, 0, 0, 0]
   
 0 0  1. 2  
[0,0, 1, 1]

-1 -2 -1 0
-1-1 1 1


 [-1,1, -1, 1]
0 -1 0. -1. 0  

because ask the max length, so only when key doesn't exist, update the hashmap
if (!map.containsKey(sum)) {
    map.put(sum, i);
}

T: O(n)
S: O(n)
*/

more clear one

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