每日OJ题_算法_前缀和⑥_力扣974. 和可被 K 整除的子数组

本文主要是介绍每日OJ题_算法_前缀和⑥_力扣974. 和可被 K 整除的子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

解析代码

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

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

难度中等

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。

子数组 是数组的连续部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
2 <= k <= 10^4

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {}
};

解析代码

和上一篇博客力扣560. 和为 K 的子数组的原理一样，只是要多了解两个知识：

①同余定理。②C++对负数取模的修正。

同余定理：数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系（即a % m == b % m）。

数学中的取余法则，即两个数取余，余数总是为正数。

C++/Java中负数对正数取余的结果是负数，所以要修正：

C++取模：当被除数为负数时取模结果为负数，需要纠正 -> (x % k + k) % k;

如C++中 -10 % 7 = -3（-10 + 7 * 1 = 3），而数学中 -10 % 7 = 4（-10 + 7 * 2 = 4）

所以在C++中要手动修正成-> （-10 % 7 + 7）% 7 = 4。

理解上面两个知识之后代码就和上一篇博客力扣560. 和为 K 的子数组的差不多一样了：

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int n = nums.size(), sum = 0, ret = 0;;unordered_map<int, int> hash(n); // 左存前缀和对k取模的余数，右存前缀和出现次数hash[0 % k] = 1;for(int i = 0; i < n; ++i){sum += nums[i];int remainder = (sum % k + k) % k;if(hash[remainder] != 0){ret += hash[remainder];}hash[remainder]++;}return ret;}
};

这篇关于每日OJ题_算法_前缀和⑥_力扣974. 和可被 K 整除的子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！