Saturday, January 12, 2019
974. Subarray Sums Divisible by K
Version #1 Prefix sum + mod
有一个特别需要注意的地方
java对负数的mod比较特殊,不遵循数学上的定义
-2 % 5 = -2 但实际上 -2 % 5 = 3 所以为了保持一致,要在mod的结果上加上K然后再mod就做到了结果为正数
60.00 %
class Solution {
public int subarraysDivByK(int[] A, int K) {
// prefixSum
// 5 % 4 = 1, 9 % 4 = 1
// (5 - 9) % 4 = 0
// we are looking for a previous prefix that has the same mod result with current prefix
// If we use a map to count how many previous prefixSum that has the mod same to current prefixSum, then we know current prefixSum can be paired with all of those prefix prefixSums
// modK
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0;
int result = 0;
for (int i = 0; i < A.length; i++) {
sum = ((sum + A[i]) % K + K) % K;
int modCount = map.getOrDefault(sum, 0);
result += modCount;
map.put(sum, modCount + 1);
}
return result;
}
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment