30-Day LeetCoding Challenge (Day13)

來到第二週的第六天，果然又出現了 Medium 難度的題目了：525. Contiguous Array（大膽猜測明天會出現新題目）

今天的題目是要找出連續最長的子序列，這個子序列中 0/1 個數相同。

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

一開始的思路是先掃過一次陣列，把每個時間點的 0/1 個數分別記起來→找出最大的相等值→再從頭一個一個刪，直到暴力的看完每個選項。
不過這個雖然自己跑一些測資都通過，但因為時間需要Ｏ(Ｎ)，最後就ＴＬＥ啦。

int findMaxLength(vector<int>& nums) {
    if(nums.empty())
        return 0;

    vector<vector<int> > cnt(nums.size(), vector<int>(2,0));
    int maxLength = 0;

    cnt[0][nums[0]]++;

    for(int i=1; i<nums.size(); i++){
        cnt[i][nums[i]] = cnt[i-1][nums[i]] + 1;
        cnt[i][!(nums[i])] = cnt[i-1][!(nums[i])];
    }

    while(!nums.empty()){
        for(int i=(int)nums.size()-1; i>0; i--) {
            if(cnt[i][0] == cnt[i][1])
                if ((cnt[i][0] * 2) > maxLength)
                    maxLength = cnt[i][0] * 2;
        }

        for(int i=0; i<nums.size(); i++)
            cnt[i][nums[0]]--;

        nums.erase(nums.begin());
        cnt.erase(cnt.begin());
    }

    return maxLength;
}

借用官網解說圖片，其實我們從頭開始 Traverse 時可以有個變數紀錄：遇到０減一，遇到１加一。當同一個值重複出現就表示中間有相同的０／１個數。

修改一下程式如下，map 再度派上用場。利用 cnt 當作 key，把第一次遇到的 index 存下來。當後面再次遇到相同的 key 時，計算＆更新最大的 subarray。

int findMaxLength(vector<int>& nums) {
        if(nums.empty())
            return 0;

        int maxLength = 0;
        int cnt = 0;
        unordered_map<int, int> m;

        m[0] = -1;
        for(int i=0; i< nums.size(); i++){
            cnt += nums[i] == 0 ? -1 : 1;
            if(!m.count(cnt))
                m[cnt] = i;
            else
                maxLength = max(maxLength, i - m[cnt]);
        }

        return maxLength;
    }

Medium 果然如 30-Day LeetCoding Challenge (Day6) 心得，一個演算法好壞對成績影響甚大，這次甚至更狠的Ｏ(Ｎ)直接讓你ＴＬＥ。
就算都是用類似的概念，看下面這三個波峰時間也可以相差甚遠，果然演算法深似海啊。