給定一個整數(shù)數(shù)組 A，返回其中元素之和可被 K 整除的（連續(xù)、非空）子數(shù)組的數(shù)目。

示例：

輸入：A = [4,5,0,-2,-3,1], K = 5
輸出：7
解釋：
有 7 個子數(shù)組滿足其元素之和可被 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) {
        // 碰到連續(xù)子數(shù)組，要想到前綴和；
        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 同一個余數(shù);
        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;
    }
}