哈喽，各位，我是前端L。

在我们的DP（及其衍生技巧）探险中，“前缀和 + 哈希表”已经成为了解决“子数组和”相关问题的黄金搭档。

• 在 LC 560 中，我们用它精确统计了和等于 K 的子数组个数。

• 在 LC 523 中，我们巧妙利用模运算和哈希表，判定了是否存在和是 K 的倍数的子数组（长度至少为2）。

今天，我们将结合这两者的智慧，挑战一个“集大成”的问题：不再是判定“有没有”，而是要精确计算“有多少个”和恰好能被 K 整除的子数组。这要求我们对“同余定理”的运用，以及哈希表的计数方式，达到炉火纯青的地步。

力扣 974. 和可被 K 整除的子数组

https://leetcode.cn/problems/subarray-sums-divisible-by-k/

题目分析： 给定一个整数数组 nums 和一个整数 k，统计并返回 nums 的连续子数组中，元素和能被 k 整除的子数组的数目。

• 子数组和能被 k 整除： 子数组和 % k == 0。

• 连续：必须是挨着的。

• 目标：计数。

核心武器再升级：从“判定”到“计数”

我们再次祭出“前缀和 + 模运算”这对利器。 令 preSum[x] 为 nums[0...x-1] 的和。 子数组 nums[i...j] 的和为 preSum[j+1] - preSum[i]。 我们要找的是满足 (preSum[j+1] - preSum[i]) % k == 0 的 (i, j) 对的数量。

根据同余定理，这等价于： preSum[j+1] % k == preSum[i] % k

现在，问题转化为了：当我们遍历到 j 时，计算出当前的前缀和 currentSum = preSum[j+1] 及其余数 remainder = currentSum % k，我们需要知道，在 j 之前，有多少个索引 i，其对应的前缀和 preSum[i] 也有着相同的余数 remainder？

这正是“和为K”（LC 560）中使用哈希表的逻辑！唯一的区别是，哈希表存的不再是前缀和本身，而是前缀和的余数！

哈希表登场：记录“余数”的频率

我们需要一个哈希表 remainderFreq 来存储 {余数 -> 该余数出现过的次数}。

算法流程：

1. 初始化哈希表 remainderFreq = { {0, 1} }。

   • {0, 1} 的精妙再现: 这表示在开始遍历之前（可以看作是空前缀 preSum[0]），余数为 0 的情况已经出现了1次。这至关重要，它能正确处理那些从数组开头就满足条件的子数组（例如 nums=[k, ...]，当 j=0 时, currentSum=k, remainder=0, 我们需要 remainderFreq[0] 来计数）。

2. 初始化 count = 0 (最终结果)，currentSum = 0 (当前前缀和)。

3. 遍历数组 nums (假设当前元素为 num，下标为 j)： a. 更新 currentSum += num。 b. 计算当前的余数 remainder = (currentSum % k + k) % k。（注意：+k 再 %k是为了优雅地处理负数 currentSum 可能产生的负余数，确保 remainder 始终在 [0, k-1] 范围内）。 c. 查找并累加: 检查 remainder 是否在 remainderFreq 中。如果存在，说明在当前位置 j 之前，已经有 remainderFreq[remainder] 个前缀和，它们与 currentSum 同余 k。每一个这样的前缀和 preSum[i] 都能与当前的 preSum[j+1] 配对，形成一个和能被 k 整除的子数组 nums[i...j]。因此，我们将这些可能性全部累加到结果中：count += remainderFreq[remainder]。 d. 更新哈希表: 将当前的余数 remainder 的出现次数加1：remainderFreq[remainder]++。

4. 遍历结束后，count 就是最终答案。

代码实现

#include <vector>
#include <unordered_map>

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int count = 0;
        long long currentSum = 0; // 使用 long long 防止前缀和溢出
        // 存储 {余数 -> 出现次数}
        unordered_map<int, int> remainderFreq;
        
        // 初始化：余数0出现1次（空前缀）
        remainderFreq[0] = 1;

        for (int num : nums) {
            currentSum += num;
            
            // 计算非负余数
            int remainder = (currentSum % k + k) % k; 
            
            // 如果这个余数之前出现过，说明找到了若干个满足条件的子数组
            if (remainderFreq.count(remainder)) {
                count += remainderFreq[remainder];
            }
            
            // 将当前的余数（或更新）其频率
            remainderFreq[remainder]++;
        }
        
        return count;
    }
};

总结：“和”系列问题的“大一统”

今天这道题，可以说是“子数组和”系列问题（LC 560, LC 523, LC 974）的完美终结。它向我们展示了“前缀和 + 哈希表”这一组合技的惊人通用性和灵活性：

问题	核心条件	哈希表 Key	哈希表 Value	count 增加逻辑
LC 560 (和为K)	preSum[j+1] - preSum[i] == k	preSum	frequency	+= freq[currentSum - k]
LC 523 (存在和是K倍数, len>=2)	(preSum[j+1] - preSum[i]) % k == 0	remainder	first_index	if j - first_index >= 2 return true
LC 974 (和是K倍数计数)	(preSum[j+1] - preSum[i]) % k == 0	remainder	frequency	+= freq[currentRemainder]

通过对比，我们可以清晰地看到：

• 前缀和是处理所有连续子数组和问题的基础。

• 模运算是解决“整除”、“倍数”类问题的钥匙。

• 哈希表是实现 O(n) 复杂度的加速器。

而具体是存值还是存余数，是存频率还是存索引，则取决于问题的最终目标是“精确值计数”、“存在性判定”还是“模等计数”。

掌握了这个“大一统”的思想框架，你就拥有了秒杀绝大多数“子数组和”问题的能力！

咱们下期见~