By Long Luo

这是 Leetcode 525. 连续数组 的题解。

方法一：暴力

思路与算法：

首先想到的方法是暴力法，遍历数组，计算 \(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
22

public 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)\)。

方法二：哈希表 + 前缀和

思路与算法：

1. 创建一个 \(\texttt{HashMap}\)，用 \(key\) 来储存 \(curr\) 值，\(value\) 来储存当前 \(index\);

2. 碰到 \(0\) 就将 \(cur--\)，碰到 \(1\) 则 \(curr++\);

3. 如果能在 \(\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
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)\)，其中 \(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. 😉😃💗