给定一个整数数组 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 * 104-104 <= nums[i] <= 1042 <= k <= 104
解题思路：求余定理 + 前缀和 + 哈希表
其实这道题和 560. 和为 K 的子数组 是基本一样的，不同的是这道题需要借用一个求余定理才能配合前缀和快速地解决问题！
先说求余定理的结论：如果 (a - b) % k == 0，就能得到 a % k = b % k。例如 (25 - 5) % 4 = 0，那么就能得到 25 % 4 = 5 % 4 = 1。
和前面那道题一样，我们在求 [0, i] 数组中满足元素之和能被 k 整除的子数组，那么最后这个子数组一定是以 i 结尾的，也就是说是后半部分连续，而前半部分是不一定连续的，那么既然要使用前缀和，我们就得将其和前半部分联系起来，我们就想到了用减法了转换求解的目标，如下图所示：
那么我们因为我们要求的区间，就是 (sum - x) % k = 0，那么通过求余定理就能得到 sum % k = x % k，换句话说，我们只需要找到在 [0, i] 区间内满足前缀和余数等于 sum % k 的子数组个数，就是能被 k 整除的子数组个数！
而为了能快速找到这个目标值，那么我们就得使用哈希表，记录每次出现的 sum % k。
但是有一个问题，就是如果是【负数 % 正数】，即我们要求的 sum % k，得到的其实是一个负数，这明显不是我们想要的，但是因为 c++ 和 java 的取模结果都是这样子，所以我们要进行结果的修正！
其实很简单，因为得到了负数，我们只需要在 sum % k 之后，那么我们只需要再加上一个 k 就能将其变成一个正数，那又有一个问题，就是有可能本来 sum % k 就是【正数 % 正数】，得到的就是一个正数，如果我们多加了一个 k，那么就错了！
所以我们就需要再对上面的结果取模，得到 (sum % k + k) % k，这样子无论是正数还是负数，得到的就是我们想要的正数结果了，这也是算法题经常遇到的问题！
此外就是一些细节处理，比如哈希表我们对于一个特殊情况也就是 (sum % k + k) % k 最后如果得到了 0 的话，说明这时整个前缀和区间都是我们要求的，那么我们就需要对 0 这个特殊情况进行考虑，将 hash[0] 提前置为 1，防止漏掉了这种情况！
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 特殊处理
int sum = 0, ret = 0;
for(int i = 0; i < nums.size(); ++i)
{
sum += nums[i]; // 累加前缀和
int target = (sum % k + k) % k; // 得到一个正确的取模结果
if(hash.count(target))
ret += hash[target]; // 如果存在target说明这个区间内有满足条件的，则统计个数
hash[target]++; // 将出现的取模结果累加到哈希表中
}
return ret;
}
};