# explanation of prefixSum + HashMap method

• The same number of `1` and `0` means the number of `1` is half the total number between `i` and `j`. So we do not need to care about the number of `0` afterwords.

We need the `prefixSum` array(call this array `n[]`) which is also the number of `1`. So we need to find the maximum `j - i` such that:

`n[j] - n[i] = (j - i) / 2`
`2*n[j] - j = 2*n[i] - i`

So in the HashMap, such pair would be stored: `[2 * n[i] - i -> i]`. Once we find an existed key, the maximum would be updated.

``````public class Solution {
public int findMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int len = nums.length;
int[] sum = new int[len + 1];
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 0);

sum[0] = 0;
int max = 0;
for (int i = 1; i <= len; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
int n = 2 * sum[i] - i;
if (map.containsKey(n)) {
max = Math.max(max, i - map.get(n));
} else {
map.put(n, i);
}
}
return max;
}
}
``````

• cool!!! Thanks for your explanation.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.