By Long Luo
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;
}
复杂度分析：
- 时间复杂度：
，其中
是数组
- 空间复杂度：
空间复杂度主要取决于哈希表，哈希表中存储的不同的的值不超过
