525. Contiguous Array (Medium)

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Solution 1: HashMap O(n); O(n)

[0,1,0,0,1,0,0,1,0]

这道题给了我们一个二进制的数组，让我们找邻近的子数组使其0和1的个数相等。对于求子数组的问题，我们需要时刻记着求累积和是一种很犀利的工具，但是这里怎么将子数组的和跟0和1的个数之间产生联系呢？我们需要用到一个trick，遇到1就加1，遇到0就减1，这样如果某个子数组和为0，就说明0和1的个数相等，这个想法真是太叼了。知道了这一点，我们用一个哈希表建立子数组之和跟结尾位置的坐标之间的映射。如果某个子数组之和在哈希表里存在了，说明当前子数组减去哈希表中存的那个子数字，得到的结果是中间一段子数组之和，必然为0，说明0和1的个数相等，我们更新结果res

    /**
     * HashMap O(n); O(n)
     * use counter to record the amount of 1 more than 0
     */
    public int findMaxLength(int[] nums) {
        if (nums == null) {
            return -1;
        }

        int count = 0; //use counter to record the amount of 1 more than 0
        Map<Integer, Integer> map = new HashMap<>(); //key:counter, value:index
        map.put(0, -1); //start from count 0, where is a virtual index of -1.
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i] == 0 ? -1 : 1; //遇到1就加1，遇到0就减1
            if (map.containsKey(count)) {
                res = Math.max(res, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return res;
    }

Solution 2: DP O(n); O(n)

    public int findMaxLengthB(int[] nums) {
        // 技巧1： 让 0 的时候的数变成-1， 1 的时候还是1. 这样就可以通过记录sum 是0 的位置来判断这个subarray；
        // 技巧2： 通过Array来存这个数是否之前出现 来加快速度。
        if (nums == null) {
            return -1;
        }

        int n = nums.length;
        int[] dp = new int[n * 2 + 1];
        dp[n] = -1;
        int count = n; // 通过这个来保证他前面都是正数的index
        int res = 0;
        for (int i = 0; i < n; i++) {
//            count += nums[i] + nums[i] - 1; // 通过这个来让0 -> -1
            count += nums[i] == 0 ? -1 : 1;
            if (dp[count] == 0) {
                dp[count] = i + 1;
            } else {
                res = dp[count] == -1 ? i + 1 : Math.max(res, i + 1 - dp[count]);
            }
        }
        return res;
    }