前缀和实战：和为 K 的子数组及整除子数组解法

前缀和专题实战

在算法面试中，涉及子数组求和的问题往往可以通过前缀和 + 哈希表的组合来优化。今天重点讲解两道经典题目：LeetCode 560（和为 K 的子数组）与 974（和可被 K 整除的子数组）。

---

1. 和为 K 的子数组

核心思路：

假设 sum[i] 表示从索引 0 到 i 的前缀和。如果我们想找到以 i 结尾、和为 k 的子数组，实际上是在寻找是否存在某个起始位置 x，使得 sum[i] - sum[x-1] == k。

移项后得到：sum[x-1] == sum[i] - k。

这意味着，我们不需要维护整个前缀和数组，只需要用一个哈希表记录遍历过程中每个前缀和出现的次数。当计算到当前位置的当前前缀和 currentSum 时，直接查询哈希表中 currentSum - k 出现过的次数即可。

注意点：

初始化时，哈希表中需放入 {0: 1}。这代表前缀和为 0 的情况出现过一次（即空数组），用于处理从数组开头开始就满足条件的情况。

代码实现：

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

时间复杂度 O(n)，空间复杂度 O(n)。

---

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

这道题是上一题的变种，核心在于利用同余定理处理整除条件。

前置知识：

如果 (a - b) % n == 0，则 a % n == b % n。也就是说，两个数相减能被 n 整除，等价于它们对 n 取模的结果相同。

对于负数取模，C++ 中的 % 运算符可能返回负值（例如 ）。为了保证结果非负，统一使用公式：。