@Eliooooooo：每日一题
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
```

解法一：前缀和+哈希

时间复杂度：O(n)

空间复杂度：O(n)
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0]++;
int sum = 0, ret = 0;
for(auto e : nums)
{
sum += e;
int cur = (sum % k + k) % k;
if(hash.count(cur)) ret += hash[cur];
hash[cur]++;
}
return ret;
}
};