30-Day LeetCoding Challenge Day 13: Contiguous Array

Contiguous Array指的是「一個Array中，0與1的數字一樣多」。而這題給我們一個Array，要問我們「最長的Contiguous Array有多長」。

這題最後有說，array size 可能到5萬這麼長，所以用暴力解一定掛，想都不用想 XD

其實我們可以這麼想，如果我們追踨一個值，叫「目前為止0與1的個數差」，此值每當遇到0時就加一，遇到1時就減1，那麼，沿著Array走一遍，可以畫出如下結果：

我們可以看到，以紅色為例，在index = 3時，diff來到了3，幾經波折，在index = 5、7、11時，diff都有碰到3這個值，而距離最遠的兩個index就是[3, 11] 這個組合了，因此當diff=3時，最長contiguous array的長度為 11–3=8，而總體來說，最長的則是[0,14]這個組合，因此答案即為14–0=14

為什麼我們可以這麼解？因為：

當此刻的0與1相差 d，我們繼續往下走，差值會跟著浮動，而下一次差值又來到 d 時，代表 「這段區間的0跟1是一樣多的」。

程式如下：

public class Solution {
    public int findMaxLength(int[] nums) {

        Map<Integer, Integer> countToFirstIndex = new HashMap<>();

        int maxLength = 0;
        int count = 0;
        countToFirstIndex.put(0, -1);

        for (int i = 0; i < nums.length; i++) {

            int num = nums[i];
            count += num == 0
                    ? -1
                    : 1;

            Integer firstIndex = countToFirstIndex.get(count);

            if (firstIndex == null) {
                countToFirstIndex.put(count, i);
            } else {
                maxLength = Math.max(maxLength, i - firstIndex);
            }

        }

        return maxLength;

    }
}

Happy Coding