One pass,use a HashMap to record 0-1 count difference


  • 20
    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(zero-one)){
                    len=Math.max(len,i-map.get(zero-one));
                }else{
                    map.put(zero-one,i);
                }
            }
            
            return len;
        }
    }

  • 0
    D

    Thanks. This was very helpful.


  • 1

    nice solution without modifying current array content.


  • 0
    D

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


  • 1
        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;  
        }

Log in to reply
 

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