《算法题讲解指南：优选算法-前缀和》--29.和为k的子数组，30.和可被k整除的子数组
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
29. 和为k的子数组
题目链接：
560. 和为 K 的子数组 - 力扣（LeetCode）
题目描述：
题目示例：
解法（前缀和+哈希表）：
算法思路：
设 i 为数组中的任意位置，用 sum[ i ] 表示 【0，i】区间内所有元素的和。
想知道有多少个【以 i 结尾的和为 k 的子数组】，就要找到有多少个起始位置为 x1，x2, x3……，使得【x，i】区间内所有元素的和 k 。那么【0，x】区间内的和是不是就是 sum[ i ] - k 了。于是问题就变成：
- 找到在【0，i - 1】区间内，有多少前缀和等于 sum[ i ] - k 的即可。
我们其实也不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于 sum[ i ] - k 。因此，我们仅需要用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。
C++算法代码：
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> hash; hash[0] = 1; int count = 0; int sum = 0; for(int i = 0; i < nums.size(); i++) { sum += nums[i]; if(hash[sum - k]) { count += hash[sum - k]; } hash[sum]++; } return count; } };算法总结及流程解析：
30. 和可被k整除的子数组
题目链接：
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
题目描述：
题目示例：
解法（前缀和+哈希表）：
前置知识补充：
同余定理：
如果 (a - b) % n == 0，那么我们就可以得到一个结论：a % n == b % n。用文字叙述就是，如果两个数相减的差能够被 n 整除，那么这两个数对 n 取模的结果相同。
例如：(26 - 2) % 12 == 0，那么 26 % 12 == 2 % 12 == 2。
C++ 中负数取模的结果，以及修正【负数取模】的结果：
- C++ 中关于负数的取模运算，结果是【把负数当成正数，取模之后的结果加上一个负号】。 例如：-1 % 3 = -(1 % 3) = -1
- 因为有负数，为了防止发生【出现负数】的结果，以 (a % n + n) % n 的形式输出保证为正。例如：-1 % 3=（-1 % 3 + 3）% 3 = 2
算法思路：
思路与上一题类似
设 i 为数组中的任意位置，用 sum[ i ] 表示 【0，i】区间内所有元素的和。
- 想知道有多少个【以 i 为结尾的可被 k 整除的子数组】，就要找到有多少个起始位置为 x1，x2，x3…… ，使得【x，i】区间内所有元素的和可被 k 整除。
- 设【0，x - 1】区间内所有元素之和等于 a ，【0，i】区间内所有元素的和等于 b，可得： （b - a）% k == 0 。
- 由同余定理可得，【0，x - 1】区间与【0，i】区间内的前缀和同余。于是问题就变成：找到在【0，i - 1】区间内，有多少前缀和的余数等于 sum[ i ] % k 的即可
这里我们也不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于 sum[ i ] % k。但是这个我们需要处理一下，确保不会为负数。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。
C++算法代码：
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, int> hash; int count = 0; int sum = 0; int rem = 0; hash[0] = 1; //这里的0表示i位置前缀和正好被k整除 for(auto i : nums) { sum += i; rem = sum % k; if(rem < 0) //负数 % 正数 -> 负数 —> 需要修正为正数 -> 负数+k { rem += k; } if(hash[rem]) //同余定理：(a - b)/p = k -> (a - b)%p == 0 -> a%p == b%p { count += hash[rem]; } hash[rem]++; } return count; } };算法总结及流程解析：
结束语
到此，29.和为k的子数组，30.和可被k整除的子数组 这两道算法题就讲解完了。两道题均采用前缀和+哈希表方法，通过统计前缀和出现的次数来快速计算符合条件的子数组数量。第二题在类似思路基础上结合同余定理，处理了负数取模问题。希望大家能有所收获！
