「优选算法刷题」：和可被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

二、思路解析

这也是一道求和的题，这一类大部分都可以用前缀和进行优化。

另外，这道题还涉及了一个小定理：同余定理，还有其修正，具体请看下图👇

同余定理：
如果 (a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。⽤⽂字叙述就是，如果两个数相减的差能被 n 整除，那么这两个数对?n?取模的结果相同。

例如： (26 - 2) % 12 == 0 ，那么 26 % 12 == 2 % 12 == 2.

而关于负数 % 正数的结果修正，这是因为它的结果恒为负数，修正则是为了让他的结果变成正数。

例如： -1 % 3 = (-1 % 3 + 3) % 3 = 2.

所以在这道题，我们还得创建一个哈希表，用于记录在 i 位置之前，保存到哈希表 [ 0 , i - 1 ] 位置的余数 [ 即 (sum % k + k ) % k ] 的值。

同余定理在这道题的运用，其实就是在帮助我们完成如下等量代换👇

于是问题就变成：
找到在 [0, i - 1] 区间内，有多少前缀和的余数等于 sum[ i ] % k 的。

三、完整代码

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        hash.put(0 % k , 1);
        int ret = 0;
        int n = nums.length;
        int sum = 0;
        for(int x : nums){
            sum += x;
            int r = (sum % k + k) % k;
            ret += hash.getOrDefault(r , 0);
            hash.put(r , hash.getOrDefault(r , 0) + 1);
        }
        return ret;
    }
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！