前缀和(和可被K整除的子数组)(6)
https://blog.csdn.net/2601_95366422/article/details/158841676
上节课链接
一.题目
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
二.思路
2.1 错误思路
这题同样不可以使用滑动窗口，和上一题和为k的子数组一样的问题！
2.2 重要知识讲解
同余定理：如果两个数a和b的差能被k整除，那么它们对k取余的结果相等，即
(a−b)%k==0 ⟺ a%k == b%k
修正求余：在C++中，负数对正数取余的结果是负数（例如-1 % 5 = -1），这与数学上的余数定义不同。因此需要修正，修正公式为：
mod = (sum % k + k) % k
2.3 正确思路
我们采用前缀和 + 哈希表的方法。定义前缀和sum为从数组起始到当前位置的累加和。根据同余定理，子数组[j+1, i]的和能被k整除等价于sum[i] % k == sum[j] % k。因此，我们只需要统计有多少对前缀和的余数相等。
遍历数组，计算当前前缀和sum，并用修正公式得到当前余数mod。然后，在哈希表中查找之前出现过多少次相同的mod，这些次数就是能与当前位置构成合法子数组的个数，累加到答案中。最后将当前mod的出现次数加一，供后续使用。
三.代码演示
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int,int>hash; 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_map<int, int>）来记录前缀和对 k 取余的结果出现的次数。在遍历数组之前，我们预先在哈希表中存入hash[0] = 1，这表示余数为 0 已经出现过一次（对应空数组的前缀和）。这个初始化至关重要，因为它能正确处理那些从数组开头开始且和能被 k 整除的子数组。同时，定义两个变量：sum用于累加当前的前缀和，初始为 0；ret用于统计满足条件的子数组个数，初始为 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 整除”转化为“两个前缀和的余数相等”，从而将问题转化为统计相同余数出现的对数。