【数据结构-前缀哈希】力扣525. 连续数组

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

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

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

class Solution { public:     int findMaxLength(vector<int>& nums) {         for(int &num : nums){             if(num == 0){                 num = -1;             }         }             int sum = 0,res = 0;         unordered_map<int, int> group;         for(int i = 0;i < nums.size();i++){             sum += nums[i];             if(sum == 0){                 res = i + 1;             }             if(group.contains(sum)){                 res = max(res, i - group[sum]);             }             else{                 group[sum] = i;             }         }         return res;     } }; 

时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历数组一次。
空间复杂度：O(n)

将nums中的0全部替换成-1，然后定义一个哈希表group，键用来储存sum，值用来储存对应的前缀和的下标。当前计算前缀和sum的时候，如果前面有相同的前缀和，说明中间这个子段和为0，也就说明0和1的数量相等，所以这个时候i - group[sum]来求这个子段的长度。然后不断比较求的0和1数量相等的最大子段长度。