Java solution O(n) one pass with HashMap with explanation


  • 1
    G

    solution:

    • keep a variable count, iterate through nums, if we get a 0, count minus 1, else count add 1
    • use a hashmap to record the position of count
    • If current count is not in hashmap, push (count, i) (where i is the location)

    What if the map already contains this count?

    Let's say map.get(count) = p, that means, from p to i, we have equal number of 0s and 1s. Then we get a valid solution.

    What's more, we don't need to put this position in map because we want the subarray as long as possible.

    public class Solution {
        public int findMaxLength(int[] nums) {
            Map<Integer, Integer> pos = new HashMap<>();
            int count = 0, res = 0;
            pos.put(0, -1);
            for (int i = 0; i < nums.length; i ++) {
                // small trick, avoid using condition
                count += (nums[i] << 1) - 1;
                if (pos.containsKey(count)) {
                    res = Math.max(res, i - pos.get(count));
                } else {
                    pos.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.