LeetCode 974: Subarray Sums Divisible by K (Prefix Remainder Frequency)
LeetCode 974Prefix SumHash MapToday we solve LeetCode 974 - Subarray Sums Divisible by K.
Source: https://leetcode.com/problems/subarray-sums-divisible-by-k/
English
Problem Summary
Given an integer array nums and an integer k, return the number of non-empty subarrays whose sum is divisible by k.
Key Insight
If two prefix sums have the same remainder modulo k, their difference is divisible by k. So for each prefix remainder r, add how many times r has appeared before.
Algorithm
- Maintain running prefix sum remainder rem.
- Normalize remainder with ((rem % k) + k) % k to avoid negatives.
- Keep frequency map/count array for each remainder.
- For current remainder r, add freq[r] to answer, then increment freq[r].
Complexity Analysis
Let n be array length.
Time: O(n).
Space: O(k).
Common Pitfalls
- Forgetting initial freq[0] = 1 for subarrays starting at index 0.
- Forgetting remainder normalization for negative sums.
- Using nested loops and getting O(n²).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] freq = new int[k];
freq[0] = 1;
int ans = 0;
int rem = 0;
for (int x : nums) {
rem = (rem + x) % k;
if (rem < 0) rem += k;
ans += freq[rem];
freq[rem]++;
}
return ans;
}
}func subarraysDivByK(nums []int, k int) int {
freq := make([]int, k)
freq[0] = 1
ans, rem := 0, 0
for _, x := range nums {
rem = (rem + x) % k
if rem < 0 {
rem += k
}
ans += freq[rem]
freq[rem]++
}
return ans
}class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
vector<int> freq(k, 0);
freq[0] = 1;
int ans = 0, rem = 0;
for (int x : nums) {
rem = (rem + x) % k;
if (rem < 0) rem += k;
ans += freq[rem];
freq[rem]++;
}
return ans;
}
};from typing import List
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
freq = [0] * k
freq[0] = 1
ans = 0
rem = 0
for x in nums:
rem = (rem + x) % k
ans += freq[rem]
freq[rem] += 1
return ansvar subarraysDivByK = function(nums, k) {
const freq = new Array(k).fill(0);
freq[0] = 1;
let ans = 0;
let rem = 0;
for (const x of nums) {
rem = ((rem + x) % k + k) % k;
ans += freq[rem];
freq[rem]++;
}
return ans;
};中文
题目概述
给定整数数组 nums 和整数 k，返回和能被 k 整除的非空子数组数量。
核心思路
如果两个前缀和对 k 取模后的余数相同，那么它们之差一定能被 k 整除。也就是当前余数 r 出现时，可与之前所有余数为 r 的前缀配对。
算法步骤
- 维护前缀和余数 rem。
- 用 ((rem % k) + k) % k 归一化，避免负余数问题。
- 用频次数组/哈希表记录每个余数出现次数。
- 每次先把 freq[rem] 加入答案，再执行 freq[rem]++。
复杂度分析
设数组长度为 n。
时间复杂度：O(n)。
空间复杂度：O(k)。
常见陷阱
- 忘记初始化 freq[0] = 1，会漏掉从下标 0 开始的子数组。
- 负数参与时未归一化余数，导致计数错误。
- 使用双重循环，复杂度退化为 O(n²)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] freq = new int[k];
freq[0] = 1;
int ans = 0;
int rem = 0;
for (int x : nums) {
rem = (rem + x) % k;
if (rem < 0) rem += k;
ans += freq[rem];
freq[rem]++;
}
return ans;
}
}func subarraysDivByK(nums []int, k int) int {
freq := make([]int, k)
freq[0] = 1
ans, rem := 0, 0
for _, x := range nums {
rem = (rem + x) % k
if rem < 0 {
rem += k
}
ans += freq[rem]
freq[rem]++
}
return ans
}class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
vector<int> freq(k, 0);
freq[0] = 1;
int ans = 0, rem = 0;
for (int x : nums) {
rem = (rem + x) % k;
if (rem < 0) rem += k;
ans += freq[rem];
freq[rem]++;
}
return ans;
}
};from typing import List
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
freq = [0] * k
freq[0] = 1
ans = 0
rem = 0
for x in nums:
rem = (rem + x) % k
ans += freq[rem]
freq[rem] += 1
return ansvar subarraysDivByK = function(nums, k) {
const freq = new Array(k).fill(0);
freq[0] = 1;
let ans = 0;
let rem = 0;
for (const x of nums) {
rem = ((rem + x) % k + k) % k;
ans += freq[rem];
freq[rem]++;
}
return ans;
};
Comments