前缀和算法实战：和为 K 的子数组

前缀和算法实战：和为 K 的子数组

问题描述

今天我们来聊聊经典的「和为 K 的子数组」问题。题目要求在一个整数数组中，找出所有和为给定值 K 的连续子数组的数量。

核心要点

• 子数组必须是数组元素的连续非空排列。
• 数组元素可能包含正数、负数和零。这一点非常关键，它直接决定了我们能否使用滑动窗口等常见技巧。

解题思路

暴力解法的局限

最直观的想法是枚举所有可能的子数组，计算它们的和并与 K 比较。这需要三层循环：两层确定左右边界，一层求和。时间复杂度高达 O(N³)，对于稍大的数据量显然无法接受。

为什么滑动窗口行不通？

之前做过的双指针或滑动窗口题目，往往依赖窗口信息的单调性来降低遍历复杂度。比如只有正数时，右指针移动和会增大，左指针移动和会减小。

但本题数组中包含 0 和负数，导致求和结果不再具有单调性。我们无法通过简单的指针移动来保证窗口内和的变化趋势，因此双指针的思路在这里只能放弃。

前缀和 + 哈希表

对于数组求和问题，我们还有一个强有力的工具：前缀和。

我们可以将数组抽象成一条折线，方便观察区间关系。假设当前遍历到位置 i，其前缀和为 sum[i]。如果存在一个起始位置 j（j < i），使得从 j+1 到 i 的子数组和为 K，那么必然满足：

sum[i] - sum[j] = K

即：

sum[j] = sum[i] - K

这意味着，只要我们在遍历过程中，能够快速统计出之前出现过多少次等于 sum[i] - K 的前缀和，就能知道以当前位置结尾、和为 K 的子数组有多少个。

核心逻辑

1. 维护前缀和：遍历数组时累加当前元素得到 current_sum。
2. 查找匹配：在哈希表中查找是否存在键值为 current_sum - K。如果存在，说明之前有若干位置的前缀和与当前位置构成和为 K 的子数组，累加对应的次数。
3. 更新哈希表：将当前的 current_sum 记录到哈希表中，供后续位置查询使用。

细节处理

• 初始化：我们需要考虑一种特殊情况，即子数组从索引 0 开始。此时 sum[i] - K 应该等于 0。因此，在遍历开始前，需要在哈希表中预先存入 {0: 1}，表示前缀和为 0 出现过一次（虚拟的前缀）。
• 顺序问题：必须先统计再更新哈希表。如果先更新再统计，当 K=0 时，当前的 sum[i] 会立刻被计入，导致误判自身与自身的差值为 0，这不符合子数组的定义。
• 动态统计：不需要一次性算出所有前缀和，边遍历边统计即可。这样既节省空间，又能保证只统计了当前元素之前的有效前缀。

代码实现

基于上述思路，我们用 C++ 来实现这个高效的解法。代码逻辑清晰，重点在于哈希表的维护时机。

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 哈希表用于存储前缀和出现的次数
        unordered_map<int, int> prefixSumCount;
        
        // 初始化：前缀和为 0 出现 1 次，处理从索引 0 开始的子数组
        prefixSumCount[0] = 1;
        
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            // 更新当前前缀和
            currentSum += num;
            
            // 如果存在 (currentSum - k)，说明找到了符合条件的子数组
            if (prefixSumCount.count(currentSum - k)) {
                count += prefixSumCount[currentSum - k];
            }
            
            // 将当前前缀和加入哈希表，供后续位置使用
            prefixSumCount[currentSum]++;
        }
        
        return count;
    }
};

总结

这道题是前缀和应用的经典案例。通过引入哈希表，我们将查找历史前缀和的时间复杂度从 O(N) 降到了 O(1)，整体算法复杂度优化至 O(N)。在处理包含负数的数组求和问题时，前缀和配合哈希表往往比滑动窗口更具通用性。

掌握这种'当前状态 + 历史状态匹配'的思维模式，对解决很多变体问题（如和可被 K 整除的子数组）都很有帮助。