LeetCode 525. 连续数组 前缀和题解。加深理解前缀和思想。
525. 连续数组#
https://leetcode.cn/problems/contiguous-array/
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
前缀和#
本题实质上与 LeetCode 560. 和为 K 的子数组 题解 类似。只不过本题的k==0。
1 - 1 == 0 ，因此将0求和时处理为-1，正好可以抵消1对和的作用。
计数时也可以考虑使用int值处理，1 0 一方+1计数，一方-1计数，目的是为了统计双方进度。
当我们对数组元素求前缀和，对0、1需做消除处理，如题解中将0视为-1，前后两个前缀和一致时，也就是：
1
|
preSumSecond - preSumFirst == 0
|
说明此时，两个前缀的区间差正好是 含有相同数量的 0 和 1 的最长连续子数组。
理解前缀和，本质上是理解前缀和两段间的差。
同时本题还需get到抵消的关键点。
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
static class PreSumArr {
/*
* 执行用时：
* 43 ms
* , 在所有 Java 提交中击败了
* 5.69%
* 的用户
* 内存消耗：
* 48.9 MB
* , 在所有 Java 提交中击败了
* 99.28%
* 的用户
* 通过测试用例：
* 564 / 564
*/
/**
* 前缀和计算：
* 将0视为-1，计算前缀和时，和等于0时，满足题干所求情况。
* 多个前缀和等于0时，判断最大间距即可。
*/
public int findMaxLength(int[] nums) {
int n = nums.length;
int[] preSumArr = new int[n + 1];
// 记录某前缀和最开始出现的位置，idx表示 preSumArr 中的下标
Map<Integer, Integer> preSum2StartIdx = new HashMap<>();
preSum2StartIdx.put(0, 0);
int maxLen = 0;
for (int i = 0; i < n; i++) {
int preSumIdx = i + 1;
preSumArr[preSumIdx] = preSumArr[i] + replaceZero(nums[i]);
// 前缀和a - 前缀和b == 0 时，说明中间区间01成对
// 当前前缀和
int preSumCurr = preSumArr[preSumIdx];
if (preSum2StartIdx.containsKey(preSumCurr) && preSum2StartIdx.get(preSumCurr) != preSumIdx) {
maxLen = Math.max(maxLen, preSumIdx - preSum2StartIdx.get(preSumCurr));
}
preSum2StartIdx.putIfAbsent(preSumArr[preSumIdx], preSumIdx);
}
return maxLen;
}
/**
* 将0视为-1
*/
private int replaceZero(int num) {
return num == 1 ? 1 : -1;
}
}
|
观察上方代码，发现前缀和数组其实无需存在，只需维护一个当前前缀和数值即可。
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
34
35
36
37
38
39
40
41
42
43
44
45
|
static class PreSum {
/**
* 执行用时：
* 48 ms
* , 在所有 Java 提交中击败了
* 5.69%
* 的用户
* 内存消耗：
* 49.8 MB
* , 在所有 Java 提交中击败了
* 85.99%
* 的用户
* 通过测试用例：
* 564 / 564
*/
public int findMaxLength(int[] nums) {
int n = nums.length;
Map<Integer, Integer> preSum2StartIdx = new HashMap<>();
preSum2StartIdx.put(0, 0);
int maxLen = 0;
int preSum = 0;
for (int i = 0; i < n; i++) {
// 计算前缀和
preSum += zero2Negative(nums[i]);
// 前缀和下标位置
int preSumIdx = i + 1;
// 前置已经有前缀和与当前前缀和一致时，计算间距
Integer startIdx = preSum2StartIdx.get(preSum);
if (startIdx != null && startIdx != preSumIdx) {
maxLen = Math.max(maxLen, preSumIdx - startIdx);
}
preSum2StartIdx.putIfAbsent(preSum, preSumIdx);
}
return maxLen;
}
private int zero2Negative(int num) {
return 0 == num ? -1 : num;
}
}
|
复杂度分析#
整个过程对入参数组遍历一次，时间复杂度O(n)。
额外使用了map存储前缀和->开始下标关系，占用n的空间。
空间复杂度O(n)。