前缀和与哈希表：解决和为 K 及整除子数组问题

前缀和与哈希表：解决和为 K 及整除子数组问题

在处理连续子数组相关的问题时，前缀和往往能带来 O(N) 的时间复杂度优化。今天主要聊聊两个经典案例：LeetCode 560 和 974。它们都利用了哈希表来存储历史状态，从而避免重复计算。

和为 K 的子数组

这道题的核心在于转化。假设当前位置的前缀和是 sum[i]，如果存在某个之前的位置 x，使得 sum[i] - sum[x] == k，那么从 x+1 到 i 的子数组和就是 k。

这意味着我们只需要在遍历过程中，维护一个哈希表，记录每个前缀和出现的次数。对于当前的 sum，去查表里有没有 sum - k，有的话就把对应的次数累加到结果里。

注意初始化 hash[0] = 1，这是为了处理从数组开头就开始满足条件的情况。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1; // 初始前缀和为 0，出现一次
        int count = 0;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if(hash.count(sum - k)) {
                count += hash[sum - k];
            }
            hash[sum]++;
        }
        return count;
    }
};

这里有个小细节，直接用 hash[sum - k] 访问可能会插入默认值 0，虽然不影响计数，但用 count 方法更严谨一些，不过原逻辑也没错。关键是理解'当前和减去之前某个和等于目标值'这个转换。

和可被 K 整除的子数组

第二题稍微绕一点，涉及到同余定理。如果两个数的差能被 K 整除，那它们对 K 取模的结果一定相同。

也就是 (sum[i] - sum[x]) % k == 0 等价于 sum[i] % k == sum[x] % k。

所以思路变成了统计余数相同的次数。但在 C++ 里，负数取模的结果可能是负数（比如 -1 % 3 结果是 -1），这会导致同余判断失效。我们需要统一修正为正数，公式通常是 (a % n + n) % n。