0和1个数相同的子数组

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

1.暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ans = 0;
        for (int j = 0; j < nums.size(); ++j) {
            int sum = 0;
            for (int i = j; i >= 0; --i) {
                if (nums[i] == 1) sum++;
                else sum--;
                if (sum == 0) ans = max(ans, j - i + 1);
            }
        }
        return ans;
    }
};

程序超时，看来这题对时间复杂度的要求很高，需要牺牲空间复杂度换时间复杂度降低。

2.前缀和+哈希

  1. 在预处理前缀和时，将 nums[i] 为 0 的值当做 −1 处理
  2. 从而将问题转化为：如何求得最长一段区间和为 0 的子数组，使用哈希表来记录某个前缀和出现的最小下标是多少。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ans = 0;
        int len = nums.size();

        //1.前缀和数组初始化
        int *prefix = new int[len + 10]();
        for (int i = 1; i <= nums.size(); ++i) prefix[i] = prefix[i - 1] + (nums[i - 1] == 0 ? -1 : 1);

        //2.开始统计在 0 ~ j 中 prefix数组中有多少值为 prefix - k的数
        unordered_map<int, int> unmap;
        unmap[0] = 0;

        for (int i = 1; i <= len; ++i) {
            int temp = prefix[i];
            if (unmap.count(temp)) ans = max(ans, i - unmap[temp]);
            if (!unmap.count(temp)) unmap[temp] = i;
        }
        return ans;
    }
};

由于「000 和 111 的数量相同」等价于「111 的数量减去 000 的数量等于 000」，我们可以将数组中的 000 视作 −1-1−1，则原问题转换成「求最长的连续子数组，其元素和为 000」。

设数组 nums\textit{nums}nums 的长度为 nnn，将数组 nums\textit{nums}nums 进行转换得到长度相等的新数组 newNums\textit{newNums}newNums：对于 0≤i<n0 \le i<n0≤i<n，当 nums[i]=1\textit{nums}[i]=1nums[i]=1 时 newNums[i]=1\textit{newNums}[i]=1newNums[i]=1，当 nums[i]=0\textit{nums}[i]=0nums[i]=0 时 newNums[i]=−1\textit{newNums}[i]=-1newNums[i]=−1。

为了快速计算 newNums\textit{newNums}newNums 的子数组的元素和，需要首先计算 newNums\textit{newNums}newNums 的前缀和。用 prefixSums[i]\textit{prefixSums}[i]prefixSums[i] 表示 newNums\textit{newNums}newNums 从下标 000 到下标 iii 的前缀和，则 newNums\textit{newNums}newNums 从下标 j+1j+1j+1 到下标 kkk（其中 j<kj<kj<k）的子数组的元素和为 prefixSums[k]−prefixSums[j]\textit{prefixSums}[k]-\textit{prefixSums}[j]prefixSums[k]−prefixSums[j]，该子数组的长度为 k−jk-jk−j。

当 prefixSums[k]−prefixSums[j]=0\textit{prefixSums}[k]-\textit{prefixSums}[j]=0prefixSums[k]−prefixSums[j]=0 时，即得到 newNums\textit{newNums}newNums 的一个长度为 k−jk-jk−j 的子数组元素和为 000，对应 nums\textit{nums}nums 的一个长度为 k−jk-jk−j 的子数组中有相同数量的 000 和 111。

实现方面，不需要创建数组 newNums\textit{newNums}newNums 和 prefixSums\textit{prefixSums}prefixSums，只需要维护一个变量 counter\textit{counter}counter 存储 newNums\textit{newNums}newNums 的前缀和即可。具体做法是，遍历数组 nums\textit{nums}nums，当遇到元素 111 时将 counter\textit{counter}counter 的值加 111，当遇到元素 000 时将 counter\textit{counter}counter 的值减 111，遍历过程中使用哈希表存储每个前缀和第一次出现的下标。

规定空的前缀的结束下标为 −1-1−1，由于空的前缀的元素和为 000，因此在遍历之前，首先在哈希表中存入键值对 (0,−1)(0,-1)(0,−1)。遍历过程中，对于每个下标 iii，进行如下操作：

如果 counter\textit{counter}counter 的值在哈希表中已经存在，则取出 counter\textit{counter}counter 在哈希表中对应的下标 prevIndex\textit{prevIndex}prevIndex，nums\textit{nums}nums 从下标 prevIndex+1\textit{prevIndex}+1prevIndex+1 到下标 iii 的子数组中有相同数量的 000 和 111，该子数组的长度为 i−prevIndexi-\textit{prevIndex}i−prevIndex，使用该子数组的长度更新最长连续子数组的长度；

如果 counter\textit{counter}counter 的值在哈希表中不存在，则将当前余数和当前下标 iii 的键值对存入哈希表中。

由于哈希表存储的是 counter\textit{counter}counter 的每个取值第一次出现的下标，因此当遇到重复的前缀和时，根据当前下标和哈希表中存储的下标计算得到的子数组长度是以当前下标结尾的子数组中满足有相同数量的 000 和 111 的最长子数组的长度。遍历结束时，即可得到 nums\textit{nums}nums 中的有相同数量的 000 和 111 的最长子数组的长度。

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
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int maxLength = 0;
        unordered_map<int, int> mp;
        int counter = 0;
        mp[counter] = -1;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 1) {
                counter++;
            } else {
                counter--;
            }
            if (mp.count(counter)) {
                int prevIndex = mp[counter];
                maxLength = max(maxLength, i - prevIndex);
            } else {
                mp[counter] = i;
            }
        }
        return maxLength;
    }
};