枚举（学武功的马步）

啥是枚举？说白了，就是“挨个儿试”。这种思路，简单直接，甚至有点“暴力”。但你可别小看它，很多神级解法，都是从这个最笨的思路开始，一步步优化出来的。它就像是咱们学武功的马步，虽然枯燥，但却是根基。

光说理论没意思，咱们直接上个题，在题中去感受枚举的魅力和优化的快感。

---

问题：最长累加和为K的子数组

题目描述： 给定一个整型数组 arr 和一个整数 k，求 arr 的所有子数组中，累加和等于 k 的最长子数组长度是多少。

举个例子： arr = [1, -1, 5, -2, 3], k = 3 累加和为 3 的子数组有 [1, -1, 3] 和 [5, -2]，长度分别是 3 和 2。所以最长的长度是 3。

arr = [-2, -1, 2, 1], k = 1 累加和为 1 的子数组有 [-1, 2] 和 [1]，长度分别是 2 和 1。所以最长的长度是 2。

拿到这个题，我的第一反应是啥？就是枚举。怎么枚举？一个子数组由什么确定？不就是由它的左边界和右边界确定的嘛。那咱们就把所有可能的左右边界组合都试一遍，不就完事儿了？

解法一：最纯粹的暴力枚举

这是最直观的思路。子数组 arr[i..j]，咱们就让 i 从 0 变到 N-1，j 从 i 变到 N-1，这样就枚举出了所有的子数组。对于每一个子数组，咱们再把它里面的数加起来，看看是不是等于 k。

思路剖析：

1. 用一个变量 i 作为子数组的左边界，从 0 开始遍历。

2. 对于每个 i，用一个变量 j 作为子数组的右边界，从 i 开始遍历。

3. 这样，[i, j] 就构成了一个子数组。

4. 然后，再用一个循环，把 arr[i] 到 arr[j] 的所有数加起来，得到 sum。

5. 如果 sum == k，就用 j - i + 1 这个长度去更新我们的最大长度 maxLen。

代码实现：

public static int getMaxLength1(int[] arr, int k) {
    int maxLen = 0;
    // i 是子数组的左边界
    for (int i = 0; i < arr.length; i++) {
        // j 是子数组的右边界
        for (int j = i; j < arr.length; j++) {
            // 下面这个循环是计算 arr[i..j] 的和
            int sum = 0;
            for (int l = i; l <= j; l++) {
                sum += arr[l];
            }
            if (sum == k) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
}

分析一下： 这个解法，三层循环，时间复杂度妥妥的 O(N³)。在 N 比较大的时候，肯定会超时。它虽然能解决问题，但效率太低了。

咱们得优化。优化的第一步，就是找重复计算。你看，当咱们固定了 i，j 从 i 移动到 i+1 时，arr[i..i] 的和我们算了一遍，arr[i..i+1] 的和我们又重新算了一遍。实际上 arr[i..i+1] 的和不就是 arr[i..i] 的和加上 arr[i+1] 吗？这就有优化的空间了。

解法二：枚举 + 前缀和（优化版枚举）

基于上面的发现，咱们可以砍掉一层循环。当我们固定左边界 i，让右边界 j 从 i 开始向右移动时，sum 是可以累加的，没必要每次都从 i 重新算。

思路剖析：

1. 用 i 遍历，作为子数组的左边界。

2. 对于每个 i，初始化 currentSum = 0。

3. 用 j 从 i 开始遍历，作为子数组的右边界。

4. 每次循环，currentSum += arr[j]，这个 currentSum 就是 arr[i..j] 的和。

5. 如果 currentSum == k，更新 maxLen。

代码实现：

public static int getMaxLength2(int[] arr, int k) {
    int maxLen = 0;
    // i 是子数组的左边界
    for (int i = 0; i < arr.length; i++) {
        int currentSum = 0;
        // j 是子数组的右边界
        for (int j = i; j < arr.length; j++) {
            currentSum += arr[j];
            if (currentSum == k) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
}

分析一下： 这次变成了两层循环，时间复杂度降到了 O(N²)。比 O(N³) 好多了，但还能不能更快？

O(N²) 的瓶颈在于，我们枚举了所有的子数组。要想达到 O(N)，通常就不能枚举所有子数组了。思路必须得有一个飞跃。

解法三：思维飞跃！前缀和 + 哈希表

咱们换个角度想问题。当我们在数组中从左到右遍历，到达 i 位置时，我们能轻松得到 0 到 i 的累加和，我们称之为 preSum[i]。

现在，我们想找一个以 i 结尾的、累加和为 k 的子数组。这个子数组假设是从 j 开始的，也就是 arr[j..i]。那么它的累加和就是 preSum[i] - preSum[j-1]。

我们想要 preSum[i] - preSum[j-1] == k。 稍微变个形，就是 preSum[j-1] == preSum[i] - k。

这个公式是什么意思？ 当咱们遍历到 i 位置时，只要我们能找到一个最早出现的位置 j-1，使得它的前缀和恰好等于 preSum[i] - k，那么 j 到 i 这个子数组的累加和就是 k！

“找到一个最早的位置”，这不就是哈希表最擅长干的事儿吗？

思路剖析：

1. 创建一个哈希表 map，用来存储 <某个前缀和, 这个前缀和最早出现的位置>。

2. 初始化 map，放入 (0, -1)。这很关键，它表示累加和为 0 在 -1 位置就出现了。这可以处理子数组从 0 位置开始的情况。比如 arr[0..i] 的和恰好是 k，那么 preSum[i] - k 就是 0，我们就能在 map 里找到 -1，长度就是 i - (-1)。

3. 从左到右遍历数组，维护一个当前的前缀和 sum。

4. 在 i 位置：

   • 计算 sum += arr[i]。

   • 在 map 中查找是否存在 sum - k 这个键。

   • 如果存在，说明找到了一个满足条件的子数组。它的起始位置是 map.get(sum - k) + 1，结束位置是 i。长度为 i - map.get(sum - k)。用这个长度去更新 maxLen。

   • 检查当前的 sum 是否在 map 中。如果不在，就把 (sum, i) 这对键值放入 map。注意：如果 sum 已经存在，不要更新它，因为我们要的是最早出现的位置，这样才能保证找到的子数组最长。

代码实现：

import java.util.HashMap;

public static int getMaxLength3(int[] arr, int k) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    // key: 某个前缀和
    // value: 这个前缀和最早出现的位置
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1); // 这个初始化是神来之笔

    int maxLen = 0;
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (map.containsKey(sum - k)) {
            maxLen = Math.max(maxLen, i - map.get(sum - k));
        }
        // 如果 sum 不在 map 中，才记录
        // 保证了 map 记录的是每个 sum 最早出现的位置
        if (!map.containsKey(sum)) {
            map.put(sum, i);
        }
    }
    return maxLen;
}

分析一下： 我们只遍历了一遍数组，哈希表的增删查改都是 O(1) 的，所以总的时间复杂度是 O(N)。空间复杂度因为使用了哈希表，是 O(N)。这已经是这个问题的最优解了。

拓展思考：如果数组中全是正数呢？

上面的解法三，非常通用，不管数组里是正数、负数还是 0，都能搞定。但算法面试经常有个套路：给你加一些限制条件，看看你能不能想到更优的解。

如果题目加一个条件：arr 中所有元素均为正数。那该咋办？

当数组全是正数时，子数组的累加和就有了单调性。也就是说，当我们把子数组的右边界向右扩时，和一定变大；左边界向右缩时，和一定变小。

这种单调性，就是滑动窗口大显身手的最佳时机！

滑动窗口思路：

1. 用两个指针 L 和 R 表示窗口的左右边界 [L..R]。

2. R 指针不断向右移动，扩大窗口，windowSum 不断累加 arr[R]。

3. 当 windowSum > k 时，说明窗口内的和太大了，需要缩小。于是 L 指针向右移动，windowSum 减去 arr[L]。

4. 当 windowSum == k 时，找到了一个满足条件的窗口，用 R - L + 1 更新 maxLen。此时，L 也要向右移动，继续寻找下一个可能的解。

5. 当 windowSum < k 时，说明窗口内的和还不够，R 指针继续向右移动。

代码实现：

public static int getMaxLength4_Positive(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return 0;
    }

    int L = 0;
    int R = 0;
    int windowSum = 0;
    int maxLen = 0;

    // R 不断向右探索
    while (R < arr.length) {
        windowSum += arr[R];
        // 当窗口和大于 k，L 需要收缩
        while (windowSum > k) {
            windowSum -= arr[L];
            L++;
        }
        // 此时 windowSum <= k
        if (windowSum == k) {
            maxLen = Math.max(maxLen, R - L + 1);
        }
        R++;
    }
    return maxLen;
}

分析一下： L 和 R 指针都只从左到右走了一遍，没有回退，所以时间复杂度是 O(N)。没有用额外的哈希表，空间复杂度是 O(1)。在数组全是正数的特定场景下，这个解法比哈希表法在空间上更优。

---

最后总结一下

你看，从一个最简单的“枚举”，我们走过了这样一条路：

1. O(N³) 暴力枚举： 最无脑，但也最稳妥的起点。

2. O(N²) 优化枚举： 通过减少重复计算，干掉一层循环。

3. O(N) 前缀和+哈希表： 思维上的一次飞跃，从“找子数组”变成了“找两个前缀和的差值”，这是降维打击。

4. O(N) 滑动窗口： 在特定条件下（单调性），利用双指针实现空间最优解。

这整个过程，就是咱们提升算法思维的核心路径。从暴力解开始，分析它的瓶颈，然后利用数据结构（哈希表）或者问题本身的特性（单调性）去打破这个瓶颈。

所以，永远不要鄙视那个写出暴力解的自己，因为那是通往神级优化的第一步。