560. 和为K的子数组#

生活中的算法#

你有没有这样的经历：每天往存钱罐里存一些零钱，某一天突然想知道，从哪天开始存到哪天结束，刚好能凑够买一件心仪物品的钱？这其实就是在寻找”和为特定值的连续数字序列”。

这个问题在金融分析、数据处理等领域都有着广泛的应用。比如分析股票的累计收益，寻找特定增长区间；或是在气象数据中寻找累计降雨量达到特定值的时间段。

问题描述#

题目目标#

给你一个整数数组 nums 和一个整数 k，请统计并返回数组中和为 k 的连续子数组个数。

示例 1#

输入： nums = [1,1,1], k = 2 输出： 2 子数组示意：

满足条件的连续子数组:
- nums[0..1] = [1,1]
- nums[1..2] = [1,1]

text

说明： 一共有两个连续子数组的元素和等于 2，因此答案是 2。

补充说明#

这里统计的是“连续子数组”，不能打乱顺序或跳过元素。
数组中可能出现负数，因此不能直接用普通双指针替代前缀和思路。

最直观的解法：暴力枚举法#

最容易想到的方法是：枚举所有可能的子数组，计算它们的和，统计等于k的个数。

让我们用一个例子来模拟这个过程：

nums = [1,2,3], k = 3

检查所有子数组：
[1] -> sum = 1 ≠ 3
[1,2] -> sum = 3 = 3 ✓
[1,2,3] -> sum = 6 ≠ 3
[2] -> sum = 2 ≠ 3
[2,3] -> sum = 5 ≠ 3
[3] -> sum = 3 = 3 ✓

找到两个和为3的子数组

plaintext

这种思路可以用Java代码这样实现：

public int subarraySum(int[] nums, int k) {
    int count = 0; // 统计和为 k 的连续子数组个数

    // 枚举每个子数组的起点 start
    for (int start = 0; start < nums.length; start++) {
        int sum = 0; // 记录从 start 到当前 end 的累加和
        // 固定起点后，依次扩展终点 end
        for (int end = start; end < nums.length; end++) {
            sum += nums[end]; // 把 nums[end] 加入当前子数组和
            // 如果当前区间 [start, end] 的和恰好等于 k，则找到一个合法子数组
            if (sum == k) {
                count++; // 合法答案数量 +1
            }
        }
    }

    return count; // 返回最终统计结果
}

java

优化解法：前缀和 + 哈希表#

仔细观察会发现，我们在计算子数组之和时做了很多重复计算。实际上，我们可以使用前缀和的概念来优化。更妙的是，我们可以结合哈希表来快速找到符合条件的子数组。

前缀和的原理#

前缀和是到当前位置为止所有数的和。如果两个前缀和之差为k，那么这两个位置之间的子数组和就是k。

算法步骤（伪代码）#

初始化哈希表，记录前缀和出现的次数
初始化前缀和为0，计数为1（空数组的前缀和）
遍历数组，对于每个位置：
- 更新前缀和
- 查找是否存在前缀和等于(当前前缀和-k)的记录
- 更新哈希表中前缀和的出现次数

示例运行#

让我们用nums = [1,2,1,2], k = 3模拟这个过程：

初始状态：
前缀和Map = {0:1}
count = 0

1. 处理1：
   前缀和 = 1
   查找Map中是否有key为(1-3)=-2的记录：无
   更新Map = {0:1, 1:1}

2. 处理2：
   前缀和 = 3
   查找Map中是否有key为(3-3)=0的记录：有，count += 1
   更新Map = {0:1, 1:1, 3:1}

3. 处理1：
   前缀和 = 4
   查找Map中是否有key为(4-3)=1的记录：有，count += 1
   更新Map = {0:1, 1:1, 3:1, 4:1}

4. 处理2：
   前缀和 = 6
   查找Map中是否有key为(6-3)=3的记录：有，count += 1
   更新Map = {0:1, 1:1, 3:1, 4:1, 6:1}

plaintext

Java代码实现#

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixSumCount = new HashMap<>(); // key: 前缀和，value: 该前缀和出现的次数
    prefixSumCount.put(0, 1); // 初始化“前缀和为0出现1次”，表示空前缀，便于处理从下标0开始的子数组

    int count = 0; // 记录和为 k 的子数组总数
    int prefixSum = 0; // 从数组开头累加到当前位置的前缀和

    for (int num : nums) {
        prefixSum += num; // 把当前元素纳入前缀和

        // 若存在某个历史前缀和 = prefixSum - k，则两者之间的子数组和就是 k
        // 该前缀和出现几次，就新增几个合法子数组
        count += prefixSumCount.getOrDefault(prefixSum - k, 0);

        // 记录当前前缀和出现次数，供后续位置继续匹配使用
        prefixSumCount.put(prefixSum, 
            prefixSumCount.getOrDefault(prefixSum, 0) + 1);
    }

    return count; // 返回所有满足条件的连续子数组个数
}

java

解法比较#

让我们比较这两种解法：

暴力枚举法：

时间复杂度：O(n²)
空间复杂度：O(1)
优点：直观易懂
缺点：效率低，有大量重复计算

前缀和 + 哈希表法：

时间复杂度：O(n)
空间复杂度：O(n)
优点：一次遍历就能得到结果
缺点：需要额外空间存储前缀和信息

题目模式总结#

这道题体现了几个重要的算法思想：

前缀和技巧：通过预处理简化区间和的计算
哈希表应用：用于快速查找满足条件的值
空间换时间：通过存储中间结果来提高效率

这种解题模式在很多问题中都有应用，比如：

和为k的最长子数组
连续数组（0和1数量相等）
矩阵区域和检索

解决此类问题的通用思路是：

考虑是否可以通过预处理简化重复计算
思考如何利用已计算的结果
关注数值之间的关系转换
考虑边界情况的处理

小结#

通过这道题，我们不仅学会了如何找到和为k的子数组，更重要的是掌握了前缀和这个强大的预处理技巧，以及如何巧妙地结合哈希表来优化查找过程。

记住，当遇到需要频繁计算区间和的问题时，前缀和往往是一个很好的切入点。而当我们需要快速判断某个值是否存在时，哈希表常常能带来惊喜！