974. Subarray Sums Divisible by K (https://leetcode.com/problems/subarray-sums-divisible-by-k/): Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

974. Subarray Sums Divisible by K (#1 Array + Hash table).java

// Array + Hash table solution: store prefix sum mod in table as we counting; combination of 560 & 523
// Time: O(n), 19ms
// Space: O(k), 45.2mb
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int ans = 0;
        
        // Init map of <sum % K, count>
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        
        int sum = 0;
        for(int i = 0; i < A.length; i++) {
            sum += A[i];
            int mod = sum % K;
            if(mod < 0) mod += K; // !!: nums in A could be negative
            
            if(map.containsKey(mod)) {
                ans += map.get(mod);
            }
            
            map.put(mod, map.getOrDefault(mod, 0) + 1);
        }
        
        return ans;
    }
}