本文概览：本文以LeetCode经典题目"和为K的子数组"为例，从暴力解法入手，逐步优化到前缀和+哈希表解法，系统讲解如何利用前缀和将子数组和转化为两个前缀和之差，再通过哈希表将时间复杂度从 O(n²) 优化到 O(n)

一、题目

和为K的子数组

二、题目分析

给定一个整数数组 nums 和一个整数 k，统计并返回数组中和为 k 的子数组的个数

目标：找到所有连续子数组，使其元素之和等于 k，返回满足条件的子数组个数

核心概念：子数组是连续的

子数组要求元素在原数组中连续，这一特性使得我们可以利用前缀和来优化

思路概览

Java实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int subarraySum(int[] nums, int k) {
    // 存储前缀和及其出现的次数
    Map<Integer, Integer> map = new HashMap<>();
    // 初始化
    map.put(0, 1);
    int res = 0;
    int sum = 0;
    for (int num : nums) {
        sum += num;
        if (map.containsKey(sum - k)) {
            res += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return res;
}

思路简要说明

  1. 前缀和：sum 记录从数组开头到当前位置的累加和，即前缀和

  2. 转化问题：子数组 nums[j+1..i] 的和为 pre[i] - pre[j]，要让它等于 k，即 pre[i] - pre[j] = k，等价于 pre[j] = pre[i] - k

  3. 哈希表查找：我们不需要求出具体各个子数组的和，只需要看当前前缀和减去 k 后，是否存在对应的前缀和曾经在哈希表中记录过。如果有，就说明存在 pre[i] - pre[j] = k，即存在和为 k 的子数组

三、思路详解

暴力解法入手

最自然的想法是：枚举所有可能的子数组，计算每个子数组的和，判断是否等于 k

具体来说，用双重循环枚举所有子数组的起点和终点，对每个子数组求和并判断

显然可以得出以下结论

  • 时间复杂度：O(n²)，枚举所有子数组起点和终点
  • 核心瓶颈：每次确定一个新的起点后，都要重新遍历求和，大量重复计算
  • 关键思考：子数组是连续的，能否利用连续性来优化？

前缀和 + 哈希表解法

前缀和的思想

既然子数组是连续的，我们就可以采取前缀和的思想。定义前缀和数组 pre，其中 pre[i] 表示 nums[0] 到 nums[i] 的累加和

那么，子数组 nums[j+1..i] 的和就可以用两个前缀和之差来表示：

1
nums[j+1..i] 的和 = pre[i] - pre[j]

这样，我们就把"求子数组的和"转化为了"求两个前缀和之差"

从暴力前缀和到哈希表优化

有了前缀和之后，暴力做法变为：双重循环枚举 i 和 j，判断 pre[i] - pre[j] == k。时间复杂度仍然是 O(n²)

但我们进一步观察目标等式：

1
2
pre[i] - pre[j] = k
pre[j] = pre[i] - k

也就是说，对于当前位置 i 的前缀和 pre[i]，我们只需要知道在 i 之前有没有前缀和等于 pre[i] - k。如果有，就说明存在一个 j 使得 pre[i] - pre[j] = k

所以我们不需要求出具体各个子数组的和，只需要计算当前前缀和减去 k 后，有没有对应的前缀和在之前出现过

这就自然引出了哈希表：用哈希表记录每个前缀和出现的次数。遍历数组时，每计算出一个前缀和 sum，先检查 sum - k 是否在哈希表中存在，如果有就把对应的次数加到结果中，然后再把当前 sum 加入哈希表

为什么要记录出现次数而不是只记录是否存在？

因为同一个前缀和值可能出现多次。例如 nums = [1, -1, 1, -1]，k = 0，前缀和序列为 [1, 0, 1, 0]，其中前缀和 0 出现了两次，前缀和 1 也出现了两次。当遍历到第二个 0 时，sum - k = 0，此时哈希表中 0 已经出现了 1 次，说明有 1 个子数组的和为 k；当遍历到第二个 1 时，sum - k = 1，哈希表中 1 已经出现了 1 次，又有 1 个。所以必须记录次数，才能统计所有满足条件的子数组

为什么要初始化 map.put(0, 1)？

这是为了处理子数组从索引 0 开始的情况。如果 pre[i] == k，即从数组开头到 i 的子数组和就等于 k，此时 pre[i] - k = 0，我们需要在哈希表中找到前缀和 0。但此时还没有任何前缀和被加入哈希表，所以需要提前放入 0 → 1，表示"前缀和为 0 出现了 1 次"（即还没有任何元素时的初始状态）

举例：nums = [1, 1, 1], k = 2，遍历到第二个元素时 sum = 2，sum - k = 0，如果没有初始化 map.put(0, 1)，就找不到这个 0，漏掉子数组 [1, 1]

举例说明

以 nums = [1, 2, 3], k = 3 为例

步骤 num sum sum - k 哈希表（加入前） 是否包含 sum-k res 哈希表（加入后）
初始 - 0 - {0:1} - 0 {0:1}
1 1 1 -2 {0:1} 否 0 {0:1, 1:1}
2 2 3 0 {0:1, 1:1} 是，次数=1 1 {0:1, 1:1, 3:1}
3 3 6 3 {0:1, 1:1, 3:1} 是，次数=1 2 {0:1, 1:1, 3:1, 6:1}

最终结果为 2

对应的子数组为 [1, 2]（sum=3, sum-k=0, 前缀和0在位置0处）和 [3]（sum=6, sum-k=3, 前缀和3在位置1处）

  • 时间复杂度：O(n)，只需遍历一次数组，哈希表操作 O(1)
  • 空间复杂度：O(n)，哈希表最多存储 n 个不同的前缀和