974. Subarray Sums Divisible by K

Version #1 Prefix sum + mod
有一个特别需要注意的地方
java对负数的mod比较特殊，不遵循数学上的定义
-2 % 5 = -2 但实际上 -2 % 5 = 3 所以为了保持一致，要在mod的结果上加上K然后再mod就做到了结果为正数

60.00 %
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        // prefixSum
        // 5 % 4 = 1, 9 % 4 = 1
        // (5 - 9) % 4 = 0
        // we are looking for a previous prefix that has the same mod result with current prefix
        // If we use a map to count how many previous prefixSum that has the mod same to current prefixSum, then we know current prefixSum can be paired with all of those prefix prefixSums
        // modK
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            sum = ((sum + A[i]) % K + K) % K;
            int modCount = map.getOrDefault(sum, 0);
            result += modCount;
            map.put(sum, modCount + 1);
        }
        return result;
       
    }
}