算法：525.连续数组

标题

链接：leetcode

思绪分析（前缀和）

首先先容一个小本领
在处置惩罚二进制数组的时间，因为数组内里只有0和1，我们可以将所有的0变成-1
这个时间1和-1之间就可以产生很多抵消，有利于处置惩罚数组。
在该题中，要探求一个连续子数组，使得此中含有相同数量的0和1,0变成-1之后，也就是，含有相同数量的-1和1，
那么这个区间的和就是0
分析到这里，信赖读者可以联想到前面的一道题
传送门：和为K的子数组
在这道标题内里就是和为0的子数组
也就是我们必要再 [0 , i - 1] 这个区间内里探求一个最短的前缀和即是 sum - 0
处置惩罚的大体思绪类似，仍旧采用前缀和+哈希表来处置惩罚。
   细节：
  

• 哈希表内里存什么？
  哈希表内里存前缀和和这个前缀和最早出现的下标
  
• 什么时间插入哈希表
  当然是先查找，再插入
  
• 对于[0 , i ]区间恰好有相同个0和1怎样处置惩罚
  也就是这个时间我们必要特殊区处置惩罚hash[0]，hash[0]的下标固定给-1，来应对整个区间恰好有相同个0和1的情况
  
• 怎样求最长连续子数组的长度
  直接用当前位置的下标 - 前缀和对应的下标 （千万不要再加1，我们不必要包括前缀和的最后一个元素）
  
• 遇到重复的前缀和怎么处置惩罚
  遇到重复的前缀和，只记录前缀和第一次出现时的下标，才能，满意最长连续子数组
  

  代码

1. int findMaxLength(vector<int>& nums) {
2.         //类似和为K的最长子数组--和为0的最长子数组
3.         unordered_map<int,int> hash;//sum 和 下标
4.         hash[0] = -1;
5.         int sum = 0,len = 0;
7.         for(int i = 0;i < nums.size();++i)
8.         {
9.             if(nums[i] == 0) nums[i] = -1;//0和1不好处理，换成1和-1非常好处理
10.             sum += nums[i];
11.             if(hash.count(sum))
12.             len = max(len, i - hash[sum]);
13.             if(!hash.count(sum)) hash[sum] = i;//统计最早出现的
14.         }
16.         return len;
17.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。