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实际上好像不行。Solution答案如下。

brute force

brute force的写法是判断每个subarray是否满足条件，但是怎么遍历每个subarray呢？其实也是值得参考的：

    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;
    }

我感觉内层循环也能写成从0到start来做。

O(n)做法

第一种是利用数组，O(2n+1)，我没看；看了第二种Map的方法，看了Solutions里的动画挺容易理解的，照着它的动画实现了一下代码。不过我感觉过段时间还是会忘。

    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<>();
        //对于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;
    }