Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

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
推 SiranuiFlare: 大師