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]

提示：

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        // 碰到连续子数组，要想到前缀和；
        int[] preSum = new int[A.length+1];
        for(int i=0;i<A.length;i++){
            preSum[i+1] = preSum[i]+A[i];
        }
        // (preSum[j]-preSum[i])%K==0 则满足条件;
        // preSum[j]%K ~ preSum[j]%K 同一个余数;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<preSum.length;i++){
            preSum[i] = (preSum[i] % K + K) % K;
            int value = map.getOrDefault(preSum[i],0);
            map.put(preSum[i],value+1);
        }
        int res = 0;
        for(int i :map.keySet()){
            int value = map.get(i);
            int temp = (value)*(value-1)/2;
            res += temp;
        }
        return res;
    }
}