05 August 2008
给定一个整数数组 nums 和一个整数 k，返回总和可被 k 整除的非空子数组的数量。
子数组是数组的连续部分。
define sum[i, j] as sum from nums[i] to nums[j] for 0 < i < j,
sum[i + 1, j]
= sum[0, j] - sum[0, i]
= q1 * K + r1 - (q2 * K + r2)
= (q1 - q2) * k + (r1 - r2)
so sum[i + 1, j] is divisible by K if r1 == r2
We calculate all possible r’s and map them to their counts, map[r] = count, there are two situations:
r != 0, then count * (count - 1) / 2 subarrays found
r == 0, the sum itself is divisible by k, thencount subarrays found
Please note that when calculate sum % K for sum < 0, we keep adding K to sum until sum is above 0 then mod K.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int subarraysDivByK(int[] A, int K) {
int count = 0;
// Map remainder to its frequency
Map<Integer, Integer> rToFreq = new HashMap<>();
// Accumulative sum
int accSum = 0;
for (int num : A) {
accSum += num;
while (accSum < 0) {
accSum += K;
}
int r = (accSum % K + K) % K;
rToFreq.put(r, rToFreq.getOrDefault(r, 0) + 1);
}
// For subarrays starting from the first element, and share the same remainder
for (int freq : rToFreq.values()) {
if (freq > 1) {
count += freq * (freq - 1) / 2;
}
}
// For subarrays starting from the first element, and sum divisible by k
count += rToFreq.getOrDefault(0, 0);
return count;
}
}