前缀和技巧实战：和为 K 及可被 K 整除的子数组统计

前缀和专题实战：和为 K 及可被 K 整除的子数组

在处理子数组求和问题时，暴力枚举往往会导致 O(n²) 甚至更差的时间复杂度。引入前缀和（Prefix Sum）配合哈希表，可以将时间复杂度优化至 O(n)。今天我们来深入探讨两个经典的前缀和变体。

1. 和为 K 的子数组

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

核心思路 假设 sum[i] 表示从索引 0 到 i 的前缀和。如果存在某个起始位置 x，使得区间 [x, i] 的和为 k，那么必然满足： sum[i] - sum[x-1] = k 即： sum[x-1] = sum[i] - k

这意味着，当我们遍历到当前位置 i 时，只需要在之前的历史前缀和中查找有多少个值等于 current_sum - k。为了高效查询，我们使用哈希表记录每个前缀和出现的次数。

关键点

• 初始化哈希表 hash[0] = 1，这代表前缀和为 0 的情况出现了一次（对应子数组从索引 0 开始的情况）。
• 遍历时累加当前元素得到 sum，检查 sum - k 是否在表中，若存在则累加计数。
• 最后将当前 sum 的次数加一。

代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1; // 初始前缀和为 0 的情况
        int n = nums.size();
        int sum = 0, ret = 0;
        
        for (auto x : nums) {
            sum += x;
            // 如果之前出现过 sum - k，说明找到了符合条件的子数组
            if (hash.count(sum - k)) {
                ret += hash[sum - k];
            }
            // 更新当前前缀和的出现次数
            hash[sum]++;
        }
        return ret;
    }
};

2. 和可被 K 整除的子数组

给定一个整数数组 nums 和一个整数 k，返回其中和可被 k 整除的非空连续子数组的数目。