By Long Luo

525. 连续数组题目如下：

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的最长连续子数组。

提示：
1 <= nums.length <= 10^5
nums[i] 不是 0 就是 1

方法一：暴力遍历

思路与算法：

首先想到的方法是暴力遍历，第一层循环，索引从到，第二层循环则是计算到到的和的数量，如果相等，则更新最大长度。

代码如下所示：

public int findMaxLength(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return 0;
    }

    int ans = 0;
    int n = nums.length;
    int zeroNum = 0;
    int oneNum = 0;
    for (int i = 0; i < n; i++) {
        zeroNum = 0;
        oneNum = 0;
        if (nums[i] == 0) {
            zeroNum++;
        } else {
            oneNum++;
        }

        for (int j = i + 1; j < n; j++) {
            if (nums[j] == 0) {
                zeroNum++;
            } else {
                oneNum++;
            }

            if (zeroNum == oneNum) {
                ans = Math.max(ans, 2 * zeroNum);
            }
        }
    }

    return ans;
}

复杂度分析：

• 时间复杂度：，其中N是数组的长度。
• 空间复杂度：，多了2个记录和的数量变量。

方法二：哈希表 + 前缀和

思路与算法：

方法一的暴力还是太慢了，涉及到连续的数组元素，第一想到的是可以使用前缀和。如果i<j，prefix[j]-prefix[j]等于j - i / 2的，则认为i到j之间0和1的个数是一样的。我们可以先计算出数组的前缀和数组，然后再遍历一遍，求出最长的子数组。

实际上这种思路还有一个更巧妙的方法：那就是将0视作-1，则原问题转换成“求最长的连续子数组，其元素和为0”。

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

如果的值在哈希表中已经存在，则取出在哈希表中对应的下标，从下标到下标的子数组中有相同数量的和，该子数组的长度为，使用该子数组的长度更新最长连续子数组的长度；

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

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

代码如下所示：

public int findMaxLength(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return 0;
    }

    int ans = 0;
    int n = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    int sum = 0;
    map.put(0, -1);
    for (int i = 0; i < n; i++) {
        if (nums[i] == 1) {
            sum++;
        } else {
            sum--;
        }
        if (map.containsKey(sum)) {
            int prevIndex = map.get(sum);
            ans = Math.max(ans, i - prevIndex);
        } else {
            map.put(sum, i);
        }
    }

    return ans;
}

复杂度分析：

• 时间复杂度：，其中是数组的长度。
• 空间复杂度：，其中是数组的长度。
  空间复杂度主要取决于哈希表，哈希表中存储的不同的的值不超过个。

原文链接：【Leetcode算法题】525. 连续数组