# 974. Subarray Sums Divisible by K 和可被 K 整除的子数组

@TOC

## # 题目描述

Given an array `A` of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by `K`.

Example 1:

``````Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
``````

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

## # 解题方法

### # 动态规划

c++代码如下：

``````class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
const int N = A.size();
vector<int> sums = {0};
for (int a : A)
sums.push_back(a + sums.back());
vector<int> dp(N + 1, 0);
int res = 0;
for (int i = 1; i <= N; ++i) {
for (int j = i - 1; j >= 0; --j) {
if ((sums[i] - sums[j]) % K == 0) {
dp[i] = dp[j] + 1;
res += dp[i];
break;
}
}
}
return res;
}
};
``````

### # 前缀和求余

``````class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
unordered_map<int, int> m;
int preSum = 0;
int res = 0;
m[0] = 1;
for (int a : A) {
preSum = (preSum + a) % K;
if (preSum < 0) preSum += K;
res += m[preSum]++;
}
return res;
}
};
``````

## # 日期

2019 年 1 月 13 日 —— 时间太快了