(sum %= k) 974. Subarray Sums Divisible by K

T:O(n)
S:O(k), map<remainder(0~k-1), count>

```java
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> remainderCountMap = new HashMap<>(); // remainder(0~k-1), count
        remainderCountMap.put(0, 1);

        int sum = 0;
        int result = 0;
        for (int i = 0; i < n ; i++) {
            sum += nums[i];
            int remainder = sum % k;
            if (remainder < 0) {
                remainder += k;
            }
            int count = remainderCountMap.getOrDefault(remainder, 0);
            result += count;
            remainderCountMap.put(remainder, count + 1);
        }
        return result;
    }
}


/**
prefix sum

prefix sum[0...i] % k = prefix sum[0...j]  % k

prefix sum[0...i] % k - prefix sum[0...j]  % k = 0

= prefix sum[i ... j] % k = 0
其實從結論往回推, 可以得到第一個結果 => prefix sum[0...i] % k = prefix sum[0...j]  % k , 所以可以用 hashmap 去 cache

T:O(n)
S:O(k), map<remainder(0~k-1), count>

 */

```

latest:

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // sum, count
        map.put(0, 1);
        int sum = 0;
        int result = 0;
        for (int num : nums) {
            sum += num;
            while (sum < 0) {
                sum += k;
            }
            sum %= k;

            if (map.containsKey(sum)) {
                result += map.get(sum);
            }
            map.put(sum, map.getOrDefault(sum, 0)+1);
        }
        return result;
    }
}

/***
map<sum, count>


0 1
4 1 
4 2  result = 1
4 3 result += 2 -> 3
2 1
4. 4  result += 3 -> 6
0  2. result += 1 -> 7


T: O(n)
S: O(n)
 */