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.

這題我沒做出來。以為可以用DP實(shí)際上好像不行。Solution答案如下。

brute force

brute force的寫法是判斷每個(gè)subarray是否滿足條件，但是怎么遍歷每個(gè)subarray呢？其實(shí)也是值得參考的：

    public int findMaxLength(int[] nums) {
        int maxlen = 0;
        for (int start = 0; start < nums.length; start++) {
            int zeroes = 0, ones = 0;
            for (int end = start; end < nums.length; end++) {
                if (nums[end] == 0) {
                    zeroes++;
                } else {
                    ones++;
                }
                if (zeroes == ones) {
                    maxlen = Math.max(maxlen, end - start + 1);
                }
            }
        }
        return maxlen;
    }

我感覺內(nèi)層循環(huán)也能寫成從0到start來做。

O(n)做法

第一種是利用數(shù)組，O(2n+1)，我沒看；看了第二種Map的方法，看了Solutions里的動(dòng)畫挺容易理解的，照著它的動(dòng)畫實(shí)現(xiàn)了一下代碼。不過我感覺過段時(shí)間還是會(huì)忘。

    public int findMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxLen = 0;
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        //對(duì)于count==0的情況，要取index+1跟maxLen比，所以put"0,-1"
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                count--;
            }
            if (!map.containsKey(count)) {
                map.put(count, i);
                //這樣不能處理0,1,0,1這種case
//              if (count == 0) {
//                  maxLen = i + 1;
//              }
            } else {
                maxLen = Math.max(i - map.get(count), maxLen);
            }
        }
        return maxLen;
    }