ToB企服应用市场:ToB评测及商务社交产业平台

标题: 算法：525.连续数组 [打印本页]

作者: 万有斥力 时间: 2024-10-14 09:51
标题: 算法：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，我们不必要包括前缀和的最后一个元素）
遇到重复的前缀和怎么处置惩罚
遇到重复的前缀和，只记录前缀和第一次出现时的下标，才能，满意最长连续子数组

代码

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

复制代码

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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)