连续数组

连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组

方法一：计算0和1相对数量
使用一个变量 count ，用来保存遍历数组过程中到目前为止遇到的 0 和 1 的相对数量。 遇到1 的时候，count 变量加 1 ，遇到 0 的时候 count 变量减 1

从头开始遍历数组，在任何时候，如果 count 变成了 0 ，这表示我们从开头到当前位置遇到的 0 和 1 的数目一样多。另一个需要注意的是，如果我们在遍历数组的过程中遇到了相同的 count 2 次，这意味着这两个位置之间 0 和 1 的数目一样多。

public int findMaxLength(int[] nums) {
    int res = 0, count = 0, n = nums.length;
    int[] arr = new int[2 * n + 1];//相对数量最小为-n，最大为n，存的值表示和的index
    Arrays.fill(arr, -2);//所有和都未出现过
    arr[n] = -1;//记和为0出现过
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
            count--;
        } else {
            count++;
        }
        // n + count 表示相对数量应该存放的位置，>=1表示这个和之前出现过，那么这之间的0和1数量相等
        if (arr[n + count] >= -1) {
            // 更新最长长度，i - arr[n + count]是因为arr[n + count]之后一个位置到到i数量相等，这里不需要更新arr[n + count]是因为要记第一个出现的位置，这样才会最长
            res = Math.max(res, i - arr[n + count]);
        } else {
            arr[n + count] = i;
        }  
    }
    return res;
}

方法二：HashMap
和方法一类似，只是不用arr[n*2+1]存，改用map存

public int findMaxLength(int[] nums) {
    int res = 0, count = 0, n = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
            count--;
        } else {
            count++;
        }
        if (map.containsKey(count)) {
            res = Math.max(res, i - map.get(count));
        } else {
            map.put(count, i);
        }  
    }
    return res;
}