题目链接
题目:
分析:
- 补充知识
1. 同余定理: (a-b) % p = 0即a-b能被p整除, ==> a % p = b % p
2. c++, java中 [负数 % 正数] 的结果是负数, 想要得到正确结果 ==> (a%p+p)%p - 这道题和<和为k的子数组>类似, 利用前缀和的思想, 计算以i结尾的所有子数组, 前缀和为sum[i]
- 想要找到和能被k整除的数组, 我们只需要找到在[0,i-1] 区间内, 找到有多少个前缀和能被k整除, 如图:
sum[i] - x 这段区间和能被k整除, 即 (sum[i] - x)%k = 0, 根据同余定理, sum[i] % k = x % k, 所以问题就变成, 在[0,i-1] 中找有多少个前缀和的余数 = sum[i] % k, 但是前缀和有可能为负数, 所以c++和java要修改成(sum[i] % k + k) % k - 需要统计前缀和能被k整除的个数, 所以需要用哈希表, 存放(sum[i] % k + k) % k, 及个数
-
细节:
1. 前缀和加入哈希表的时机?
因为要计算[0,i-1] 区间找有多少个前缀和的余数 = (sum[i] % k + k) % k, 所以要先更新有多少个前缀和的余数 = (sum[i] % k + k) % k 的个数, 再将sum[i]放到哈希表中
2. 不用真的创建一个前缀和数组
因为我们只需要记录和能被k整除的个数, 不需要知道下标等其他信息, 所以我们用一个变量sum记录前缀和即可, sum每次更新
3. 如果整个前缀和等于k?
如果从0到i的位置的和能被k整除, 那么在[0,i-1] 的位置寻找前缀和应该是0, 也是一种情况, 但是哈希表中存的是前缀和的余数, 所以哈希表中应该添加(0 % k,1)
代码:
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> hash = new HashMap<>();
hash.put(0 % k, 1);
int sum = 0;
int ret = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];//前缀和
int r = (sum % k + k) % k;//前缀和的余数
ret += hash.getOrDefault(r, 0);
hash.put(r, hash.getOrDefault(r, 0) + 1);
}
return ret;
}
}
