Contiguous Array

Question

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

Solution

這題不知道為什麼鬼打牆，想超級久，最後看了解答才寫出來。覺得像這種用到有點 bucket sort 概念的題目，自己目前的腦袋還轉不過來。這題的核心概念在於用一個 int count 去記錄，當遇到 1 就加一，遇到 0 就減一。當 count == 0，就表示含有同樣 0 和 1 的最大 subarray 長度為 i + 1，如果遇到 arr[count] 有 index ，那就表示當前 index 跟 arr[count] 之差為最大 subarray 長度。有兩種解法：

1. 生成一個 2n + 1 的 array，index 是 count，而 array[count] 為 index。要注意 index 的轉換（因爲 extreme condition 可能為 -n ~ n，因此 count + nums.length 才是正確的 index

2. 用 HashMap 去紀錄

    public int findMaxLength(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //<count, index>
        int maxLen = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count--;
            } else {
                count++;
            }

            if (count == 0) {
                maxLen = Math.max(maxLen, i + 1);
            } else if (count != 0 && map.containsKey(count)) {
                maxLen = Math.max(maxLen, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxLen;
    }