一.题目描述
525. 连续数组 - 力扣（LeetCode）
二.题目解析
让我们找到一个最长的数组，里面的0，1个数是相等的。
这道题依旧不能用滑动窗口解决，因为找到满足的之后，需要继续遍历。
我们可以对数组进行转换，让我们找0，1相等的数组，我们可以将0变为-1，此时问题就转变为求和为0的最长的子数组。
三.算法原理
前缀和+哈希表
经过转换，这道题就类似于求和为k的子数组了。只不过这道题需要求最长的。
我们先来分析一下满足要求的子数组与前缀和之前有什么关联：
首先满足要求的区间和为0，所以sum - x = 0。即sum = x。我们要求最长的和为0的子区间，那x区间，一定就最短且等于x。所以我们在遍历的过程中，要去寻找，前缀和等于sum的区间，且该区间还得是最短的。
接下来我们就用哈希表来存对应的前缀和x。但是key不再是前缀和出现的次数了，而是其下标。当我们知道了前缀和x的下标了，也知道i，那么所求区间的长度就等于i-dp[sum].
但是我们在遍历的过程中，可能有很多相等的sum，它们对应的下标不同，但是如果哈希表中已经有了sum，就没必要再插入了，因为后面插入的sum对应的下标更大，最终的结果就更小。
边界情况：如果此时i位置的前缀和sum刚好等于0呢？说明该区间就符合要求。此时怎么计算呢？因为最终结果ret = i - dp[sum].说明此时（0，i）这个区间满足要求，长度是i+1.而直接用公式i-mp[sum] = i.为了满足结果，所以dp[0] = -1.
时间复杂度：所有的运算都在一遍遍历的过程中完成，所以时间复杂度是O(n)
空间复杂度：空间复杂度的开销主要在于哈希表，而哈希表存储的是前缀和，所以最坏情况下，哈希表的大小为n，所以空间复杂度为O(n)
四.代码实现
// C++class Solution
{
public:int findMaxLength(vector<int>& nums){// 前缀和及该区间的长度unordered_map<int, int> mp;mp[0] = -1;int ret = 0,n = nums.size();for(int i=0, sum=0; i<n; ++i){sum += nums[i] == 0?-1:1;if (mp.count(sum)) ret = max(ret,i-mp[sum]);if(!mp.count(sum)) mp[sum] = i;}return ret;}
};# pythonclass Solution:def findMaxLength(self, nums: List[int]) -> int:mp = {0:-1}sum,ret = 0,0for i in range(0,len(nums)):sum += -1 if nums[i] == 0 else 1if sum in mp:ret = max(ret,i-mp[sum])if sum not in mp:mp[sum] = ireturn ret
