[LeetCode][525. 连续数组] 2种方法:暴力,前缀和 + 哈希表
By Long Luo
方法一:暴力
思路与算法:
首先想到的方法是暴力法,遍历数组,计算 \(0\) 和 \(1\) 的数量,如果相等,则更新最大长度 \(\textit{maxLength}\)。
代码如下所示:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public int findMaxLength(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int ans = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
int zeroCnt = 0;
int oneCnt = 0;
for (int j = i; j < len; j++) {
zeroCnt += nums[j] == 0 ? 1 : 0;
oneCnt += nums[j] == 1 ? 1 : 0;
if (zeroCnt == oneCnt) {
ans = Math.max(ans, 2 * zeroCnt);
}
}
}
return ans;
}
复杂度分析:
- 时间复杂度:\(O(N^2)\),其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度:\(O(1)\)。
方法二:哈希表 + 前缀和
思路与算法:
创建一个 \(\texttt{HashMap}\),用 \(key\) 来储存 \(curr\) 值,\(value\) 来储存当前 \(index\);
碰到 \(0\) 就将 \(cur--\),碰到 \(1\) 则 \(curr++\);
如果能在 \(\texttt{HashMap}\) 中找到当前的 \(curr\) 值,取出对应的 \(pos\),在看当前的 \(index-pos\) 是否比 \(ans\) 大,更新最优解。
很明显,当 \(0\) 与 \(1\) 数量一致时,其连续数组的和为零。因此如果知道数组前面的 \(curr\) 值是什么,则在到达该连续数组尾部时其和就不会变。因此只需要检查 \(\texttt{HashMap}\) 中是否存在其相同的 \(curr\) 值即可!
当连续数组的起始点在 \(index=0\) 时,此时最长连续数组在数组的最前方,如果不插入 \({0, -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
26public 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)\),其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度:\(O(N)\),\(\texttt{HashMap}\) 中存储的不同的 \(\textit{counter}\) 的值不超过 \(N\) 个。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗