HashMap O(n) solution


  • 0
    S
    public class Solution {
        public int findMaxLength(int[] nums) {
            if(nums == null || nums.length < 2) return 0;
            int numZero = 0;
            int numOne = 0;
            int res = 0;
            Map<Integer, int[]> map = new HashMap<>();
            for(int i = 0; i < nums.length; i++){
                if(nums[i] == 0){
                    numZero++;
                }else{
                    numOne++;
                }
                int diff = numOne - numZero;
                if(map.containsKey(diff)){
                    map.get(diff)[1] = i;
                }else{
                    map.put(diff, new int[2]);
                    map.get(diff)[0] = i;
                }
                if(diff == 0) res = i + 1;
                else{
                    int[] tmp = map.get(diff);
                    res = Math.max(res, tmp[1] - tmp[0]);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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