※ 引述《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;
: }
: };
: ```
思路:
前綴和 假如和為0 代表從頭開始皆為10相等數列 res= i+1
用字典記錄前綴和 假如出現相同之前綴和
代表該區間10數量相等
Python Code:
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
dic = {}
prefix_sum = 0
res = 0
for i in range(len(nums)):
if nums[i] == 1:
prefix_sum += 1
else:
prefix_sum -= 1
if prefix_sum == 0:
res = i+1
elif prefix_sum in dic:
res = max(res,i-dic[prefix_sum])
else:
dic[prefix_sum] = i
return res