1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> moduCount = new HashMap<>();
        int sum = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int currModulo = Math.floorMod(sum, k);
            if (currModulo == 0) {
                ans += 1;
            }
            ans += moduCount.getOrDefault(currModulo, 0);
            moduCount.put(currModulo, moduCount.getOrDefault(currModulo, 0) + 1);
        }
        return ans;
    }
}

这个题很有意思.

需要注意的是到达某个位置的时候, sum可能是负的, 而java负数除以正数取余的话得到的余数是负的. 比如a / b = c + d. 假设a小于0, b大于0. 那么c小于等于0, d小于0. 但是我们还可以表示为a / b = (c - 1) + e. 此时e就是大于0的. e的d的关系就是bc - b + e = bc + d => e = b + d.

上面可能有些绕, 我想表达的意思是, 负数除以正数取余, 可以表示为余数是正数的形式也可以表示为余数是负数的形式. 由于正数除以正数的余数是正数. 因此我们需要把负数除以正数的余数也表示为正数的形式. 这样某两个sum除以k得到的余数相同时, 二者就可以互相减去凑成subarray. 如果把负数除以k的余数表示为负数, 那么可能它能和另一个sum相减构成subarray可以满足题意但也不会被我们捕捉到.

时间复杂度:O(n)
空间复杂度:O(n)