题目地址：https://leetcode.com/problems/subarray-sums-divisible-by-k/
题目描述
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；
题目大意
在一个数组中有多少个连续子数组的和，恰好能被K整除。
解题方法
动态规划
定义DP数组，其中dp[i]代表以i结尾的能被K整除的子数组的最多个数。既然要求子数组的和，那么我们知道，肯定需要求数组累积和sums的。那么，对于sums每个位置i向前找，找到第一个差能被K整除的位置j，就停止即可。此时的dp[i] = dp[j] + 1. 题目要求的结果是sum(dp).
下面分析这个递推公式怎么来的。dp[j]表示以j位置结尾的子数组，该子数组的和能被K整除。那么当我们寻找到(sums[i] - sums[j]) % K == 0的时候，说明子数组sums[i, j]也能被K整除，那么，以i结尾的所有子数组个数等于以j结尾的子数组后面拼接上[i,j]子数组，加上[i,j]子数组.即dp[i] = dp[j] + 1。那么，为什么会break掉呢？这是因为，我们dp的状态是以i结尾的子数组的最大个数，再往前搜索则不是最大的。
这个代码的时间复杂度是O(N^2)的，也AC了，我认为主要是break的功劳。
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
前缀和求余
其实，在上面这个做法当中，我们对于每个i位置都向前去查询(sums[i] - sums[j]) % K == 0的j，找到之后立马break，这一步可以更加简化，只要我们使用前缀和，并且相同余数的和。
如果(sums[i] - sums[j]) % K == 0，说明sums[i]和sums[j]都是K的倍数，所以得出sums[i] % K == sums[j] % K。也就是说，我们找到sums[i] % K这个数字的之前的状态即可。根据上面的DP，我们知道只需要找到最后的这个结果，然后break掉的意思就是，我们只需要保存最后的状态。总之，我们需要维护一个hash_map，保存每个余数在每个位置前面，出现的次数。
刚开始时，m[0] = 1，即假设0的出现了1次。然后遍历每个数字，对前缀和+当前数字再求余，在C++里面由于负数求余得到的是负数，所以要把负余数+K才行。把字典中保存的之前的结果累计，就是结果。
想了很久为什么是加的当前数字之前的结果，而不是现在的结果？这是因为，我们当前再次遇到了这个数字，才能说明形成了一个同余的区间。所以加的永远是前面的余数存在了多少次。这样，当某个余数只出现了1次时，并不会计入到结果里。
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发