【Leetcode算法题】525. 连续数组

By Long Luo

525. 连续数组题目如下:

  1. 连续数组

给定一个二进制数组 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

方法一:暴力遍历

思路与算法:

首先想到的方法是暴力遍历,第一层循环,索引ii00nn,第二层循环则是计算到i+1i+1nn0011的数量,如果相等,则更新最大长度maxLength\textit{maxLength}

代码如下所示:

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
27
28
29
30
31
32
33
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;
}

复杂度分析:

  • 时间复杂度:O(N2)O(N^2),其中N是数组nums\textit{nums}的长度。
  • 空间复杂度:O(1)O(1),多了2个记录0011的数量变量。

方法二:哈希表 + 前缀和

思路与算法:

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

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

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

如果counter\textit{counter}的值在哈希表中已经存在,则取出counter\textit{counter}在哈希表中对应的下标prevIndex\textit{prevIndex}nums\textit{nums}从下标prevIndex+1\textit{prevIndex}+1到下标ii的子数组中有相同数量的0011,该子数组的长度为iprevIndexi-\textit{prevIndex},使用该子数组的长度更新最长连续子数组的长度;

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

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

代码如下所示:

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
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;
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度。
  • 空间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度。
    空间复杂度主要取决于哈希表,哈希表中存储的不同的counter\textit{counter}的值不超过NN个。