Finding the Largest Balanced Subarray

1. 简介

本文将介绍如何在二进制数组中找到最长的平衡子数组。所谓“平衡子数组”，指的是其中 0 和 1 的数量相等的连续子数组。

2. 问题描述

问题： 给定一个仅包含 0 和 1 的数组 A，找出其中最长的连续子数组，使得该子数组中 0 和 1 的数量相等。

举例：
输入数组为 {0, 1, 1, 0, 1, 1, 1, 0}，最长平衡子数组长度为 4，对应子数组为 {0, 1, 1, 0}。

3. 暴力解法（Brute Force）

最直接的方法是枚举所有可能的子数组，统计每个子数组中 0 和 1 的数量，判断是否相等并记录最大长度。

✅ 示例代码：

public int maxBalancedSubarrayLength(int[] A) {
    int maxLength = 0;
    int n = A.length;

    for (int i = 0; i < n - 1; i++) {
        int zeroCount = 0;
        int oneCount = 0;

        for (int j = i; j < n; j++) {
            if (A[j] == 0) zeroCount++;
            else oneCount++;

            if (zeroCount == oneCount) {
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
    }

    return maxLength;
}

⚠️ 时间复杂度：

• **O(n²)**，因为使用了两层嵌套循环遍历所有子数组。

✅ 空间复杂度：

• **O(1)**，仅使用了常数级别的变量。

❌ 缺点：

• 时间效率较低，尤其在大规模输入时会明显拖慢性能。

---

4. 哈希表优化解法（Hash Table Approach）

🧠 核心思想：

我们引入一个 counter 变量来记录当前遍历过程中 1 和 0 的相对数量（1 增加 1，0 减少 1）。

关键观察：

• 如果两个位置 i 和 j 的 counter 值相同，说明从 i+1 到 j 的子数组中 1 和 0 的数量相等。
• 因此我们可以使用哈希表来记录每个 counter 值首次出现的索引。

📌 初始化技巧：

• 我们将 counter=0 对应的索引设为 -1，以便处理从数组起始位置开始的平衡子数组。

✅ 示例代码：

public int maxBalancedSubarrayLength(int[] A) {
    Map<Integer, Integer> hashTable = new HashMap<>();
    int maxLength = 0;
    int counter = 0;

    hashTable.put(0, -1);  // 初始值

    for (int i = 0; i < A.length; i++) {
        if (A[i] == 1) {
            counter++;
        } else {
            counter--;
        }

        if (hashTable.containsKey(counter)) {
            int start = hashTable.get(counter);
            maxLength = Math.max(maxLength, i - start);
        } else {
            hashTable.put(counter, i);
        }
    }

    return maxLength;
}

📊 示例说明：

以数组 {0, 1, 1, 0, 1, 1, 1, 0} 为例，counter 值变化如下：

index	-1	0	1	2	3	4	5	6	7
A		0	1	1	0	1	1	1	0
counter	0	-1	0	1	0	1	2	3	2

• counter=0 在 index 1 和 index 3 都出现，说明从 index 2 到 index 3 是一个平衡子数组，长度为 2。
• 最长平衡子数组是 {0, 1, 1, 0}，长度为 4。

⚠️ 时间复杂度：

• **O(n)**，只遍历一次数组。

✅ 空间复杂度：

• **O(n)**，哈希表最多存储 n+1 个不同的 counter 值。

✅ 优势：

• 时间效率高，适合处理大规模输入数据。

---

5. 总结

我们介绍了两种解决“最长平衡子数组”问题的算法：

方法	时间复杂度	空间复杂度	特点
暴力解法	O(n²)	O(1)	实现简单但效率低
哈希表优化	O(n)	O(n)	时间效率高，适合大规模数据

✅ 推荐使用哈希表方法，它在性能上具有显著优势，尤其适合处理实际场景中较大的输入数据。