算法日记：从暴力到 O(n) 的线性飞跃 —— 平衡子数组问题(leetcode525)

1. 直觉：暴力 (O(n^2))

最开始拿到这道题，最直观的反应是：枚举所有的子数组。

  • 做法：双层 for 循环，外层固定起点 i，内层枚举终点 j。
  • 判断：统计 [i, j] 区间内 0 和 1 的个数是否相等。
  • 瓶颈：随着 n 的增加，计算量呈平方级增长。当 n = 10^5 时，明显超出题目规定范围。

2. 数学建模：前缀和的引入 (O(n^2))

为了优化掉内层的重复计数，我引入了前缀和。

  • 转换思维：把 0 看作 -1，把 1 看作 1。

  • 核心结论：如果一个子数组 $[i, j]$ 满足 0 和 1 的个数相等，那么它的区间和必为 0。

  • 前缀和公式：
    $$
    \text{preSum}[j + 1] - \text{preSum}[i] = 0
    $$

  • 代码实现：

// 第一版逻辑：前缀和 + 暴力查找
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        if (preSum[j + 1] - preSum[i] == 0) { // 满足平衡
            maxLen = max(maxLen, j - i + 1);
        }
    }
}
  • 发现问题：虽然计算区间和变快了，但我依然在用双重循环去”寻找”那两个相等的坐标。复杂度依然是 O(n^2)。

3. 优化：哈希表的”位置索引”(O(n))

这是最关键的突破点。我意识到我不需要去”找” j，而是在路过 i 的时候，让哈希表帮我记住它。

  • 逻辑反转：

    • 过去：固定左端点，找右端点。
    • 现在：站在右端点，回首望向最远的左端点。

  • 核心策略：
    $$
    如果 \text{preSum}[i] == \text{preSum}[j+1] 说明中间这一段抵消了。
    $$

    • 为了让子数组最长，我只需要记录每个前缀和数值 第一次 出现的位置。
    • 哈希表 first[val] 就像是一个备忘录：“嘿，海拔为 val 的地方，我最早在下标 i 见过你。”

4. 完整代码

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        // 1. 构建前缀和数组：将 0 视为 -1，1 视为 1
        vector<int> preSum(n + 1, 0);
        for (int i = 0; i < n; i++) { 
            preSum[i + 1] = preSum[i] + (nums[i] == 1 ? 1 : -1);
        }

        // 2. 引入哈希表：保存每一个不同的 preSum[i] 第一次出现的位置
        unordered_map<int, int> first;
        int maxLen = 0;

        // 3. 线性扫描：利用 preSum[i] == preSum[j] 的特性 O(n) 解决
        for (int i = 0; i <= n; i++) {
            int val = preSum[i];
            // 如果这个海拔以前见过，直接计算当前位置与最早位置的距离
            if (first.count(val)) {
                int j = first[val];
                maxLen = max(maxLen, i - j); 
            } else {
                // 如果是第一次见这个海拔，赶紧记下来
                first[val] = i;
            }
        }
        return maxLen;
    }
};

5. 算法心得总结

  • 前缀和：将”区间问题”降维成”点与点的关系”。
  • 哈希表：将”寻找关系”的时间从 O(n) 降低到 O(1)。
  • 这种组合技的套路：
    1. 看到区间求和，先想前缀和。
    2. 看到 O(n^2) 找坐标关系，必想哈希表。
    3. 别忘了初始化（比如 preSum[0] = 0 对应的下标是 0）。