题目如下：

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

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

Example 2:

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

题目大意

给定一个只包含0和1的数组，找出数组中0和1数量相等的最长子序列。

思路

将0变成-1，然后遍历整个数组，求出前面的的数字之和，同时将这个数字放在HashSet中记录，如果之后的遍历之中出现了相同的和，那么说明这一段长度内的0和1数量相等，然后把这些子序列中的长度最长的那个记录并返回即可。整个数组只遍历了一次，因此时间复杂度是O(n)，使用了HashSet记录数组和， 空间复杂度比较难分析，与输入有关，最坏情况是O(n)，最好情况是O(1)，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findMaxLength(int[] nums) {
    int sum = 0, max = 0;
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    map.put(0, -1);
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i] == 0 ? -1 : 1;
        if (map.containsKey(sum)) {
            max = max > i - map.get(sum) ? max : i - map.get(sum);
        } else {
            map.put(sum, i);
        }
    }
    return max;
}

提交AC，运行时间75ms

提交结果
提交结果

很好奇的看了下时间最短的代码，时间只有35ms，给大神们跪了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findMaxLength(int[] nums) {
    int len = nums.length;
    int[] map = new int[len*2+1]; 
    int cp = len, res = 0;
    map[cp]=1;
    for(int i=0; i<len; i++){
        cp+=2*nums[i]-1;
        if(map[cp]==0) 
            map[cp]=i+2;
        else{
            int ssl = i-map[cp]+2;
            if(res < ssl)
                res=ssl;
        }
    }
    return res;
}

大概看了代码，思路是类似于状态机。先新建一个2倍nums长度+1的数组，从新数组中间的位置开始，对于nums中每一个数，如果是0，则新数组指针往左移动一格；如果碰到了1，则指针往右移动一格。同时在新位置判断，如果此位置之前没有存储过数值，则在此位置存储i，否则说明目前为止出现过0和1数量i相等的子序列，并且起始位置即为此位置存储的i，因此直接计算子序列长度即可。依次遍历，这样就能把最长子序列求出来。该数组遍历了一次，因此时间复杂度是O(n)，使用了2*n+1长度的辅助数组，因此空间复杂度是O(n)。

提交结果
提交结果