算法：525.连续数组

题目

链接：leetcode

思路分析（前缀和）

首先介绍一个小技巧
在处理二进制数组的时候，因为数组里面只有0和1，我们可以将所有的0变成-1
这个时候1和-1之间就可以产生很多抵消，有利于处理数组。

在该题中，要寻找一个连续子数组，使得其中含有相同数量的0和1,0变成-1之后，也就是，含有相同数量的-1和1，
那么这个区间的和就是0

分析到这里，相信读者可以联想到前面的一道题
传送门：和为K的子数组

在这道题目里面就是和为0的子数组
也就是我们需要再 [0 , i - 1] 这个区间里面寻找一个最短的前缀和等于 sum - 0

处理的大体思路类似，依旧采用前缀和+哈希表来处理。

细节：

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

代码

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;
    }

原文地址：https://blog.csdn.net/2303_78940834/article/details/142893857

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！