Concise Java Code with explanation(Prefix Trick)


  • 0

    Pre:

    1. any subarray could be a subarray from 0 to j MINUS subarray from 0 to i (i < j);

    2. prefix[i] denotes the subarray from 0 to i(exclusively), so it will consider prefix[0] as empty subarray


    Now let's explain this question:

    *1. if we met a 0, we minus 1, met 1, plus 1. Let's record it for every position int the prefix sum, and call it 0/1sum.

    *2. we want to find all the subarray(which is also denotes by position: 0 ~ position(exclusively)) whose 0/1sum are same.
    Actually we only want to remember the first position, so when we get last position we could get the longest length.

    *3. so we use HashMap to record the position of the every different 0/1sum when it first appear, let's say it's "i". and when we met other same 0/1sum with different position "j", we subtract j - i to get the length. Maintain a “max” to record the max length, return it in the end.](link url)

    class Solution {
        public int findMaxLength(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            int[] prefix = new int[nums.length + 1];
            map.put(0, 0);
            int max = 0;
            for (int i = 1; i < prefix.length; i++) {
                prefix[i] = prefix[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
                if (map.containsKey(prefix[i])) {
                    max = Math.max(max, i - map.get(prefix[i]));    
                }
                if (!map.containsKey(prefix[i])) {
                    map.put(prefix[i], i);
                } 
            }
            return max;
        }
    }
    

    Together with LC 325, Framework

    class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            int[] prefix = new int[nums.length + 1];
            map.put(0, 0);
            int max = 0;
            for (int i = 1; i < prefix.length; i++) {
                prefix[i] = prefix[i - 1] + nums[i - 1];
                if (map.containsKey(prefix[i] - k)) {
                    max = Math.max(max, i - map.get(prefix[i] - k));
                }
                if (!map.containsKey(prefix[i])) {
                    map.put(prefix[i], i);
                } 
            }
            return max;
        }
    }
    

Log in to reply
 

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