※ 引述《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