算法实战：利用前缀和求解和为 K 的子数组

和为 K 的子数组

问题描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续子数组的个数。

核心难点

子数组是数组元素的连续非空排列。与通常的滑动窗口题目不同，本题数组元素有正有负，这导致求和（窗口信息）不具有单调性。因此，双指针或滑动窗口的思路在这里无法直接使用，我们需要寻找新的突破口。

解题思路：前缀和 + 哈希表

对于数组求和问题，前缀和是一个非常有力的工具。我们不需要一次性算出所有前缀和，而是可以在遍历过程中动态维护。

原理分析

假设当前遍历到的位置是 i，当前的前缀和为 sum[i]。如果存在某个位置 j (j < i)，使得 sum[j] = sum[i] - k，那么从 j+1 到 i 的子数组和必然等于 k。

换句话说，我们要统计和为 k 的子数组个数，等价于在遍历到 i 时，统计之前出现过的前缀和中，有多少个值等于 currentSum - k。

关键细节

1. 初始化：在开始遍历前，哈希表中应记录 prefixSumCount[0] = 1。这是因为如果从索引 0 开始的子数组和恰好为 k，此时 currentSum - k 为 0，需要这个初始值来匹配。
2. 顺序：必须先查询哈希表，再更新当前前缀和。如果先更新，当 k=0 时会误判自身满足条件。
3. 效率：使用哈希表可以将查找时间复杂度降为 O(1)，整体时间复杂度优化至 O(N)。

代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSumCount;
        // 初始化：前缀和为 0 的情况出现一次
        prefixSumCount[0] = 1;
        
        int count = 0;
        int currentSum = 0;
        
        for (int num : nums) {
            currentSum += num;
            
            // 检查是否存在前缀和为 currentSum - k 的位置
             (prefixSumCount.(currentSum - k)) {
                count += prefixSumCount[currentSum - k];
            }
            
            
            prefixSumCount[currentSum]++;
        }
        
         count;
    }
};