连续数组问题

连续数组问题

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((sum)) ret=max(ret,i-hash[sum]);
         else hash[sum]=i;
       }
  return ret;
    }
};