來到第二週的第六天,果然又出現了 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 個數分別記起來→找出最大的相等值→再從頭一個一個刪,直到暴力的看完每個選項。
不過這個雖然自己跑一些測資都通過,但因為時間需要O(N),最後就TLE啦。

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 時可以有個變數紀錄:遇到0減一,遇到1加一。當同一個值重複出現就表示中間有相同的0/1個數。

修改一下程式如下,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) 心得,一個演算法好壞對成績影響甚大,這次甚至更狠的O(N)直接讓你TLE。
就算都是用類似的概念,看下面這三個波峰時間也可以相差甚遠,果然演算法深似海啊。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料