525. Contiguous Array

Version #1 Prefix Diff + HashMap

class Solution {
    public int findMaxLength(int[] nums) {
// [1,1,0,1,0,0,1,1,1,0]
int countOne = 0;
int max = 0;
// int[] prefixDiff =new int[nums.length + 1];
// key-> -diff, value-> first occurrence index
Map<Integer, Integer> map = new HashMap<>();
// I'm trying to use a prefix diff to keep track of countOne in [0, i)
        map.put(0, 0); // prefix diff is 1 indexed, so prefixDiff[0] = 0
for (int i = 1; i <= nums.length; i++) {
if (nums[i -1] == 1) {
countOne++;
} else {
countOne--;
}
if (map.containsKey(countOne)) {
max = Math.max(max, i - map.get(countOne));
}
map.putIfAbsent(countOne, i);
}
return max;
}
}