【数据结构-前缀哈希】力扣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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

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