LeetCode.974.Subarray Sums Divisible by K 和可被K整除的子数组

题目描述

974 Subarray Sums Divisible by K
https://leetcode-cn.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 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

---

相似题目

LeetCode.1248.Count Number of Nice Subarrays 统计优美子数组
LeetCode.560.Subarray Sum Equals K 和为K的子数组
LeetCode.974.Subarray Sums Divisible by K 和可被K整除的子数组
523 连续的子数组和
https://leetcode-cn.com/problems/continuous-subarray-sum/

---

解题过程

哈希表存储前缀和O(n^2)

做过 560题 和为k的子数组后，一看到这个题就知道是用前缀和来做，第一个想法是哈希表存储 前缀和 和 对应的个数，从前往后遍历数组 nums，每次统计以当前元素为结尾的子数组中和是 k 的倍数的子树组个数，但是这个统计需要每次都O(n)遍历一遍哈希表，找出所有 (preSum - key) % k == 0 的 key，最终时间复杂度是 O(n^2)，空间复杂度O(n)，结果超时了。

// 哈希表存储前缀和，超时，68 / 73 个通过测试用例
private static class SolutionV202005PreSumBrutal {
    public int subarraysDivByK(int[] nums, int k) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        Map<Integer, Integer> preSumToCountMap = new HashMap<>();
        // 前缀和为 0 的子数组个数为1，目的是为了统计从开头到 i 的子数组 nums[0...i] 的信息时依然正确
        preSumToCountMap.put(0, 1);

        int res = 0;
        int preSum = 0;
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            // 统计以当前元素为结尾的子数组中和是 k 的倍数的子树组个数
            for(Map.Entry<Integer, Integer> entry : preSumToCountMap.entrySet()) {
                if ((preSum - entry.getKey()) % k == 0) {
                    res += entry.getValue();
                }
            }
            preSumToCountMap.put(preSum, preSumToCountMap.getOrDefault(preSum, 0) + 1);
        }
        return res;
    }
}

哈希表存储前缀和的模O(n)

上一个方法中，每次我们要遍历整个哈希表找出 (preSum - key)%k == 0，根据同余定理，也就是找出和 preSum 关于 k 同余的 之前的前缀和，也就是 preSum%k == key%k，所以我们直接存储每个前缀和对k的模的个数即可，然后也不需要每次遍历整个哈希表了，直接 get(preSum % k) 即可。

具体实现上，用哈希表 preSumModKToCountMap 存储前缀和的模和对应出现次数的映射，从前往后遍历 nums 数组，每次也计算 preSum 对 k 取模的结果，然后去 preSumModKToCountMap 找对对应个数累加即可。

注意：Java 中的 % 运算符是求余运算，Math.floorMod(a,b) 是取模运算。，由于前缀和可能出现负数，这里我们要用 Math.floorMod(a,b) 取模操作。
为什么呢？
举个例子，k = 5，假如之前有个前缀和是 -1 ，当前前缀和是 4
如果用 java 的 % 求余操作，则 -1%5 = -1，4%5 = 4，两者不相等，但其实 4-(-1) = 5 这个区间内的子数组的和是 5 的倍数，错了。
如果改为Math.floorMod(a,b) 取模操作，则 Math.floorMod(-1,5) = 4， Math.floorMod(4,5) = 4，两者相等，可以被正确统计。

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

// 哈希表存储前缀和mod K后的出现次数
private static class SolutionV202005PreSumModK {
    public int subarraysDivByK(int[] nums, int k) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        // 前缀和 mod k 后的出现次数
        Map<Integer, Integer> preSumModKToCountMap = new HashMap<>();
        // 前缀和为 0 的子数组个数为1，目的是为了统计从开头到 i 的子数组 nums[0...i] 的信息时依然正确
        preSumModKToCountMap.put(0, 1);

        int res = 0;
        int preSum = 0;
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            // 模
            int mod = Math.floorMod(preSum, k);
            // 统计以当前元素为结尾的子数组中和是 k 的倍数的子树组个数
            res += preSumModKToCountMap.getOrDefault(mod, 0);
            preSumModKToCountMap.put(mod, preSumModKToCountMap.getOrDefault(mod, 0) + 1);
        }
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_974_SubarraySumsDivisibleByK.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_974_SubarraySumsDivisibleByK.java

---