連續(xù)數(shù)組

給定一個(gè)二進(jìn)制數(shù)組, 找到含有相同數(shù)量的 0 和 1 的最長(zhǎng)連續(xù)子數(shù)組（的長(zhǎng)度）。

示例 1:

輸入: [0,1]
輸出: 2
說(shuō)明: [0, 1] 是具有相同數(shù)量0和1的最長(zhǎng)連續(xù)子數(shù)組。

示例 2:

輸入: [0,1,0]
輸出: 2
說(shuō)明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長(zhǎng)連續(xù)子數(shù)組

方法一：計(jì)算0和1相對(duì)數(shù)量
使用一個(gè)變量 count ，用來(lái)保存遍歷數(shù)組過(guò)程中到目前為止遇到的 0 和 1 的相對(duì)數(shù)量。 遇到1 的時(shí)候，count 變量加 1 ，遇到 0 的時(shí)候 count 變量減 1

從頭開(kāi)始遍歷數(shù)組，在任何時(shí)候，如果 count 變成了 0 ，這表示我們從開(kāi)頭到當(dāng)前位置遇到的 0 和 1 的數(shù)目一樣多。另一個(gè)需要注意的是，如果我們?cè)诒闅v數(shù)組的過(guò)程中遇到了相同的 count 2 次，這意味著這兩個(gè)位置之間 0 和 1 的數(shù)目一樣多。

public int findMaxLength(int[] nums) {
    int res = 0, count = 0, n = nums.length;
    int[] arr = new int[2 * n + 1];//相對(duì)數(shù)量最小為-n，最大為n，存的值表示和的index
    Arrays.fill(arr, -2);//所有和都未出現(xiàn)過(guò)
    arr[n] = -1;//記和為0出現(xiàn)過(guò)
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
            count--;
        } else {
            count++;
        }
        // n + count 表示相對(duì)數(shù)量應(yīng)該存放的位置，>=1表示這個(gè)和之前出現(xiàn)過(guò)，那么這之間的0和1數(shù)量相等
        if (arr[n + count] >= -1) {
            // 更新最長(zhǎng)長(zhǎng)度，i - arr[n + count]是因?yàn)閍rr[n + count]之后一個(gè)位置到到i數(shù)量相等，這里不需要更新arr[n + count]是因?yàn)橐浀谝粋€(gè)出現(xiàn)的位置，這樣才會(huì)最長(zhǎng)
            res = Math.max(res, i - arr[n + count]);
        } else {
            arr[n + count] = i;
        }  
    }
    return res;
}

方法二：HashMap
和方法一類(lèi)似，只是不用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;
}