推 sustainer123: 大師 03/17 11:04
推 TokiwaKurumi: 愛五寶 03/17 11:05
今天的做過了
補一下昨天的 恨525
525. Contiguous Array
一開始就往subarray sum想
若nums[i:j]符合條件，表示sum[i:j] == (j-i+1)/2 (整除時)
原本想說就照這個條件，記下prefix sum，每個j都往前找各個i
但看了一下size <= 50000，想當然不是這樣
後來發現其實只要把0都改成-1，
就只需要確認prefix sum與自己相等的那個地方就可以了
只需要用個map記下最早出現這個prefix sum的index即可
好像在哪裡也用過這招，有點忘記了
int findMaxLength(vector<int>& nums) {
int n = nums.size();
unordered_map<int,int> mp;
int prefix = 0;
int ans = 0;
mp[0] = -1;
for(int i=0; i<n; i++)
{
prefix += (nums[i] == 0 ? -1 : 1);
if(mp.find(prefix) != mp.end())
{
ans = max(ans, i-mp[prefix]);
}
else
{
mp[prefix] = i;
}
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710644462.A.1D7.html
※ 編輯: DJYOSHITAKA (125.228.146.144 臺灣), 03/17/2024 11:01:18