public class Solution {
public int findMaxLength(int[] nums) {
HashMap<Integer,Integer> map=new HashMap<>();
map.put(0,1);
int zero=0;
int one=0;
int len=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
zero++;
}else{
one++;
}
if(map.containsKey(zeroone)){
len=Math.max(len,imap.get(zeroone));
}else{
map.put(zeroone,i);
}
}
return len;
}
}
One pass,use a HashMap to record 01 count difference


@bxiao0801
Thanks for sharing this. Can you please explain the logic behind this solution?

public int findMaxLength(int[] nums) { int count = 0; Map<Integer, Integer> map = new HashMap();//Key:count value:index map.put(0, 1); // start from count 0, where is a virtual index of 1. int res = 0; for(int i = 0; i < nums.length; i++){ count += nums[i] == 0 ? 1 : 1; if(map.containsKey(count)){ res = Math.max(res, i  map.get(count)); // not replacing the index, the value in map will always be first index } else { map.put(count, i); } } return res; }

It can be further simplified by using just one number to record the number of diffs
zero > 0
means we have more zeros than ones
zero < 0
means we have more ones than zeros
zero == 0
means we have equal number of ones and zeros
For example, if at any indexi
we havezero = 1
, then we have 1 diff (1 more 0s than 1s), we record it in the HashMap, and if later at indexj
we meet another situation thatzero = 1
, this means from the indexi
till the indexj
, the number of 0s and 1s are the same.public class Solution { public int findMaxLength(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int max = 0; int zero = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) zero++; else zero; if (zero == 0) max = i + 1; if (!map.containsKey(zero)) map.put(zero, i); else max = Math.max(max, i  map.get(zero)); } return max; } }