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

• 初始化：我们需要考虑一种特殊情况，即子数组从索引 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 整除的子数组）都很有帮助。