优选算法——前缀和（7）：连续数组

1.上期参考代码

classSolution{public:intsubarraysDivByK(vector<int>&nums,intk){vector<int>hash(k);hash[0%k]=1;intsum=0,ret=0;for(inti=0;i<nums.size();i++){sum+=nums[i];intr=(sum%k+k)%k;ret+=hash[r]++;}returnret;}};

2.本期知识点导图

3.本期要讲解的题目是

连续数组

要点：

• 只有01
• 找0和1个数相同的连续子数组
• 返回最长的长度

4.解题

4.1 暴力解法：

暴力枚举出所有子数组，然后每个子数组再统计0和1的个数O(N³)

4.2优解

二进制数组，只有两种元素，本身就有一定的规律性，可操作性也强，典型的处理方式就是替换元素，使之具有我们想要的性质

关键思路：

本题可以把数组中的0改成-1如果子数组中0和1个数相同的话，那子数组的元素之和就是一个定值0，问题就被转化成了：求和为0的最长子数组长度

熟悉不

同我们之前做过的求和为k的子数组有相似之处又有所区别。

• 相似之处：k=0
• 区别：之前是统计个数，这次是统计子数组长度。

整体上同之前的题目差不多
只是有几个

小细节

要处理

1. 哈希表中存啥：之前我们哈希表中存的是子数组的个数，我们是用数组来模拟哈希表的现在我们要统计的是字数组的长度，哈希表中记录的应该是nums数组的元素下标。
2. 先把0换成-1
3. 在某次遍历中，如果有重复的sum符合条件，只保留第一个，因为越往后的sum，留下的子数组长度越小

如图：

4. ret的值为i与hash[sum]的差值

5. hash[0]有个默认值，i减去这个默认值应该等于此次遍历数组的整体长度，故hash[0]=-1，为啥这里就不赘述了

6. 在更新ret之前需要判断，是否存在和为0的子数组，数组无法兼顾记录下标和是否存在的功能，所以我们得使用真正的散列表：unodered_map

7. ret取所有次遍历中的最大值

代码逻辑：

1. 初始化散列表，sum和ret
   进入循环
2. 替换零
3. 维护sum
4. 判断hash[sum]是否存在，不存在再维护散列表，存在,后边就不用了

5.嗟食

如果小编写的内容对佬有帮助，还请大佬点点三连加关注哦
佬的支持就是我前进的最大动力~

期待与佬的再次相遇~