Re: [閒聊] 每日leetcode已回收
525. Contiguous Array
Given a binary array nums, return the maximum length of a contiguous subarray wi
th an equal number of 0 and 1.
題目：
給你一個01的陣列
要求你找出裡面的01數量相等的最長的子陣列
解法：
因為要相等
所以裡面的01數量會一樣
偷偷的想起前面幾天的題目
發現用前綴和的方式好像可以
創造另一個陣列 出現0的時候-1
1的時候+1
如果出現一樣的次數
就代表進入那個區間然後出來之後裡面的01數量一樣
然後只要用unordered map記錄出現的位子就好了
優化：
可以在探索陣列01的時候
順便把出現的數字放進unordered map
這樣只要遍歷一次就可以了
```cpp
class Solution {
public:
int findMaxLength(vector<int>& nums)
{
int len = nums.size();
vector<int> paper(len+1 , 0);
paper[0] = 0;
for(int i = 0 ; i < len ; i ++)
{
if(nums[i] == 0)
{
paper[i+1] = paper[i]-1;
}
else
{
paper[i+1] = paper[i]+1;
}
}
int res = 0;
unordered_map<int,int> save ;
for(int i = 0 ; i < len +1 ; i ++)
{
auto k = save.find(paper[i]);
if(k == save.end())
{
save.insert({paper[i] , i});
}
else
{
res = max(res, i - k->second );
}
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.19.55 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710559739.A.4E1.html
推
03/16 11:29,
1年前
, 1F
03/16 11:29, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 48 之 1548 篇)：