974. Subarray Sums Divisible by K

Compute running prefix sums and look at each prefix's remainder modulo k. Two prefix sums having the same remainder means the subarray strictly between them sums to a multiple of k. Maintain a hash map (or fixed-size array of length k) counting how many times each remainder has been seen, seeded with remainder 0 -> 1 to credit subarrays starting at index 0. Walk the array once: at each step compute the normalised remainder of the running sum, add the current count for that remainder to the answer, then increment the count. Normalisation is critical for negative numbers — use ((sum % k) + k) % k so that -3 with k=5 becomes 2 rather than -3, otherwise pairs across sign boundaries are miscounted.