给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

数组

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] positive = new int[k + 1];
        int[] negative = new int[k + 1];
        positive[0] = negative[0] = 1;
        int sum = 0;
        int ans = 0;
        for (int num : nums) {
            sum = (sum + num) % k;
            if (sum >= 0) {
                ans += positive[sum]++ + negative[k - sum];
            } else {
                ans += negative[-sum]++ + positive[k + sum];
            }
        }
        return ans;
    }
}

哈希表

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> dp = new HashMap<Integer, Integer>() {{
            put(0, 1);
        }};
        int sum = 0;
        int ans = 0;
        for (int num : nums) {
            sum = ((sum + num) % k + k) % k;
            int cnt = dp.getOrDefault(sum, 0);
            ans += cnt;
            dp.put(sum, cnt + 1);
        }
        return ans;
    }
}