连续数组问题
目录
一·题目：
二·思路：
三·代码：
一·题目：
leetcode链接：. - 力扣（LeetCode）
二·思路：
思路：前缀和（第二种）+化0为-1+hash：
这样可以把原题中的求子数组内零，1个数相同的最长子数组长度 转为 把0改为-1，即和为零的最长子数组长度：->这样就是前缀和为sum的最最短子数组，也就是让hash表
内key存每次遍历的sum也就是前缀和，而value存它前缀和位置的下标，这样如果遍历到某个i的位置发现此区间内存在目标，则此时该区间和为sum，目标区间为0
故一定存在前缀和为sum，故往hash去找key，发现后得到它的下标进行：i-hash[sum]（长度注意）；
当然这里还存在两个小细节问题：1.【-1,1】->这时符合题意但是sum此刻等于0，然而hash【0】没有初始化，因此让它ret等于2，故初始化为-1.
2.每次sum都要储存吗？当然不是：如果每次都存进去，假设上一次是刚比较出ret，那么此刻sum和某个位置前缀和相等，如果存进去则hash内对应下标是sum的值就会变大，也就是原数组下标变大，这时如果后面连着有出现为0的区间此时，ret跟新的就是后面那个小的区间，而真正的最长区间应该是这两个合一起，故只要比较了max那么就不能再次跟新此时的下标了
三·代码：
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int ret=0,sum=0;
unordered_map<int,int>hash;
hash[0]=-1;
for(int i=0;i<nums.size();i++){
nums[i]=nums[i]==1?1:-1;//化0为-1；
sum+=nums[i];
if(hash.count(sum)) ret=max(ret,i-hash[sum]);
else hash[sum]=i;
}
return ret;
}
};