当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.974.Subarray Sums Divisible by K 和可被K整除的子数组

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 = -14%5 = 4,两者不相等,但其实 4-(-1) = 5 这个区间内的子数组的和是 5 的倍数,错了。
如果改为Math.floorMod(a,b) 取模操作,则 Math.floorMod(-1,5) = 4Math.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


上一篇 LeetCode.394.Decode String 字符串解码

下一篇 LeetCode.076.Minimum Window Substring 最小覆盖子串

阅读
评论
1,000
阅读预计4分钟
创建日期 2020-05-27
修改日期 2020-05-27
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论