【LetMeFly】525.连续数组：哈希表 + 前缀和

力扣题目链接：https://leetcode.cn/problems/contiguous-array/

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

方法一：前缀和

为了方便，我们将000全部替换为−1-1−1

这样，“含有相同数量的−1-1−1、111的子数组”的元素之和就是000

我们计算这个数组的“前缀和”（类似于今天的上一题523.连续的子数组和），在计算的过程中，我们将“首次得到这个前缀和结果的下标记录下来”。

例如：

原始数组：[1  0  0 1  0 1 1]
用-1替换：[1 -1 -1 1 -1 1 1]
求前缀和：[1  0 -1 0 -1 0 1]↑              ↑第一次出现1      再一次出现1

来看前缀和为1的位置：

第一次前缀和为1的位置的下标为0，第二次前缀和为1的位置下标为6

这说明什么？这说明nums[1]+nums[2]+nums[3]+nums[4]+nums[5]+nums[6]=0nums[1] + nums[2] + nums[3] + nums[4] + nums[5] + nums[6] = 0nums[1]+nums[2]+nums[3]+nums[4]+nums[5]+nums[6]=0

111到666这666个元素的和为000，也就是说，111到666这666个元素中，111和−1-1−1的个数相等。

因此，我们找到了长度为“6”的“01相等的连续子数组”

我们用哈希表记录下“每个前缀和第一次得到的位置”，这样，在再次得到这个前缀和时，我们就“找到了01相等的子数组”

注意，哈希表中的初始值为[0,−1][0, -1][0,−1]，这是因为前缀和为000时，这个元素及其之前的所有元素的和为000，这些元素的个数为i+1=i−(−1)i + 1 = i - (-1)i+1=i−(−1)

• 时间复杂度O(n)O(n)O(n)，其中nnn是数组中元素的个数
• 空间复杂度O(n)O(n)O(n)

AC代码

C++

class Solution {
public:int findMaxLength(vector& nums) {unordered_map ma;int cnt = 0;ma[0] = -1;int ans = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i])cnt++;elsecnt--;if (ma.count(cnt)) {ans = max(ans, i - ma[cnt]);}else {ma[cnt] = i;}}return ans;}
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127982922