來到第二週的第六天,果然又出現了 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。
就算都是用類似的概念,看下面這三個波峰時間也可以相差甚遠,果然演算法深似海啊。