NeetCode #112LC-974MediumArrays & Hashing
← Back to All Problems#112 · #974 · Subarray Sums Divisible by K(和可被 K 整除的子数组)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return the number of non-empty subarrays whose sum is divisible by k. Constraints: 1 <= nums.length <= 2 * 10^4, -10^4 <= nums[i] <= 10^4, 2 <= k <= 10^4.💡 Core Algorithmic Approaches
- A subarray sum
nums[i..j]is divisible bykexactly when the two prefix sumsP[j+1]andP[i]are congruent modulok. - So count, for each residue, how many earlier prefixes shared it. Each such pair contributes one valid subarray.
- Maintain a hash map from residue to count, seeded with
{0: 1}to represent the empty prefix. - Python's
%always returns a non-negative result for a positive modulus, which conveniently normalises negative prefix sums.
💻 Benchmark Python3 Implementation
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
from collections import defaultdict
cnt = defaultdict(int)
cnt[0] = 1 # the empty prefix has residue 0
cur = 0
res = 0
for x in nums:
cur = (cur + x) % k # Python's % is non-negative for k > 0
res += cnt[cur] # pair with every earlier equal residue
cnt[cur] += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with O(1) average hash operations.
💾 Space Complexity
O(min(n, k)) for the residue counts.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting
cnt[0] = 1: subarrays starting at index 0 would be missed. - Worrying about negative residues: in Python
-7 % 5 == 3, so the residues are already normalised. In C++/Java you would need((cur % k) + k) % k. - Using a sliding window: it fails because the values may be negative, so the prefix sums are not monotone.
- Storing a set of residues rather than counts: two different start indices with the same residue each yield a distinct subarray, so multiplicities matter.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.