JAVA DP with o(n) beat 96%


  • 0
    T
        //make 0 as -1 then transfer the question to find maxSubArray sum is 0
        //then using dp solution 
        //O(n)time
        public int findMaxLength(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0,-1);
            int res = 0;
            int max = 0;
            for (int i = 0 ; i < nums.length; i ++) {
                res += nums[i] == 0? -1:1;
                Integer k = map.get(res);
                if (k != null) {
                    max = Math.max(i - k, max);
                }else {
                    map.put(res, i);
                }
            }
            return max;
        }
    

Log in to reply
 

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