https://blog.csdn.net/2601_95366422/article/details/158841676上节课链接一.题目974. 和可被 K 整除的子数组 - 力扣LeetCode二.思路2.1 错误思路这题同样不可以使用滑动窗口和上一题和为k的子数组一样的问题2.2 重要知识讲解同余定理如果两个数a和b的差能被k整除那么它们对k取余的结果相等即(a−b)%k0 ⟺ a%k b%k修正求余在C中负数对正数取余的结果是负数例如-1 % 5 -1这与数学上的余数定义不同。因此需要修正修正公式为mod (sum % k k) % k2.3 正确思路我们采用前缀和 哈希表的方法。定义前缀和sum为从数组起始到当前位置的累加和。根据同余定理子数组[j1, i]的和能被k整除等价于sum[i] % k sum[j] % k。因此我们只需要统计有多少对前缀和的余数相等。遍历数组计算当前前缀和sum并用修正公式得到当前余数mod。然后在哈希表中查找之前出现过多少次相同的mod这些次数就是能与当前位置构成合法子数组的个数累加到答案中。最后将当前mod的出现次数加一供后续使用。三.代码演示class Solution { public: int subarraysDivByK(vectorint nums, int k) { unordered_mapint,inthash; int sum 0; int ret 0; hash[0] 1; for(const auto x:nums) { sum x; int r (sum % k k)%k;//求余数这是修正的余数 if(hash.count(r)) ret hash[r]; hash[r]; } return ret; } };四.代码讲解一、初始化哈希表与变量首先我们需要一个哈希表unordered_mapint, int来记录前缀和对 k 取余的结果出现的次数。在遍历数组之前我们预先在哈希表中存入hash[0] 1这表示余数为 0 已经出现过一次对应空数组的前缀和。这个初始化至关重要因为它能正确处理那些从数组开头开始且和能被 k 整除的子数组。同时定义两个变量sum用于累加当前的前缀和初始为 0ret用于统计满足条件的子数组个数初始为 0。二、遍历数组并更新前缀和与余数使用范围for循环遍历数组中的每一个元素x。对于每个元素执行以下操作更新当前前缀和sum x。此时sum表示从数组起始位置到当前元素包含当前元素的累加和。计算修正后的余数由于 C 中负数取余的结果为负数为了统一比较我们需要将余数修正为非负数。计算公式为r (sum % k k) % k。这个r就是当前前缀和对 k 取余的标准结果范围在[0, k-1]。检查之前是否存在相同余数在哈希表中查找键r。根据同余定理如果之前出现过余数也为r的前缀和那么从那个位置的下一个元素到当前位置形成的子数组的和一定能被 k 整除。因此如果哈希表中存在r则将其对应的出现次数累加到结果ret中。注意这里累加的是次数因为可能有多个不同的起始位置都能与当前结束位置构成合法子数组。记录当前余数将当前余数r在哈希表中的计数加 1以便后续元素使用。这保证了之后遇到更大的下标时可以查询到当前这个余数的出现次数。三、关键细节哈希表的作用以 O(1) 的时间快速查询之前出现过多少次特定的余数将双层循环的 O(n²) 优化为 O(n)。初始化hash[0] 1的原因考虑子数组从下标 0 开始的情况此时子数组的和就是当前前缀和sum需要满足sum % k 0即余数为 0。因此我们需要在哈希表中提前存好余数 0 的出现次数为 1这样才能正确统计这类子数组。修正余数的必要性因为数组元素可能为负直接使用sum % k可能得到负数而负数无法正确映射到哈希表的索引且与数学意义上的余数不一致。通过(sum % k k) % k我们确保余数始终非负从而能正确比较。同余定理的应用核心在于将“和能被 k 整除”转化为“两个前缀和的余数相等”从而将问题转化为统计相同余数出现的对数。