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

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

示例：

输入：A = [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]

解题思路

终于理解了，主要没理解的原因是hash表具体含义。
hash表记录了前缀和的取模值出现的次数。出现一次没有任何问题，但是出现了两次以上，意味着在该值的状态下，肯定是加上了K（或者n个K）才使得最后又得到原先出现过的取模值，这个也就是官方一直强调的P[j]modK==P[i−1]modK。举例来说，
[4,5,0,-2,-3,1] ， k =5
首先会在hash表中设置一个值{0:1},具体用处下面会讲。
然后计算前缀和，
取值4
sum = 4, 然后取模，结果为4。记录哈希前缀和{0:1,4:1}，但是此时没有满足条件的子数组。
取值5
sum + 5 = 9 ,取模，结果为4。此时查找哈希表，发现4已经在之前的结果中出现了1次,这个是关键，意味着，我们进行了加操作后，增加了K（nk），才会使得又回到了4，而具体来看，其实就是加了5，所以res=[5], ans+1 = 1。而巧妙的点就在这，这个加上的1，其实就是当前查找到的4的值。更改哈希表值{0:1,4:2}
取值0
sum + 9 = 9,取模，结果为4，此时查找哈希表，发现4已经在之前的结果中出现了2次，意味着，已经有新增的k了，那么再次新增的0除了自己还可以与之前的k合成新的子数组。res = [5] [0,5] [0] ， ans +2 =3,此时的2就是当前哈希表中4对应的值，更改哈希表值{0:1，4:3}。
…..
之余一开始的{0:1}大家有也可以理解为当前缀和求模，出现0时，可以发现发现0已经在之前的结果中出现了1次，这样就和前面步骤统一了。

代码

java

class Solution {
    public HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    public int subarraysDivByK(int[] A, int K) {
        map.put(0,1);
        int sum = 0;
        int ans = 0;
        for(int a:A){
            sum += a;
            int key = (sum % K+K) %K;
            int s = map.getOrDefault(key, 0);
            ans += s;
            map.put(key, s+1);
        }
        return ans;
        

    }
}