explanation of prefixSum + HashMap method


  • 0
    C

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

  • 0
    A

    cool!!! Thanks for your explanation.


Log in to reply
 

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