Re: [閒聊] 每日leetcode已回收
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/03/17 11:01)推噓2(2推 0噓 0→)留言2則, 2人參與討論串51/1548 (看更多)
今天的做過了
補一下昨天的 恨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
推
03/17 11:04,
1年前
, 1F
03/17 11:04, 1F
推
03/17 11:05,
1年前
, 2F
03/17 11:05, 2F
討論串 (同標題文章)
完整討論串 (本文為第 51 之 1548 篇)：