974. 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. 1 <= A.length <= 30000
  2. -10000 <= A[i] <= 10000
  3. 2 <= K <= 10000

这道题给了一个数组,让返回数组的数字之和可以被K整除的非空子数组的个数。博主最开始的思路是建立累加和数组,然后就可以快速的知道任意一个子数组的数字和,从而可以判断其是否可以被K整除。但是这个方法被 OJ 残忍拒绝,说是超时 TLE 了,看来需要进一步的将平方级的复杂度优化到线性复杂度才行。说到查询的线性复杂度,那么 HashMap 是当仁不让的,可是这里该如何利用它呢。这里首先要搞懂一个规律,若子数组 [0, i] 的数字之和跟子数组 [0, j] 的数字之和对K取余相同的话,假设这里 j > i,那么子数组 [i+1, j] 的数字之和一定是可以整除K的。这里就不证明了,举个例子吧,比如 [1, 2, 3, 4],K=5,那么 [1] 之和除以5余1,[1, 2, 3] 之和除以5也余1,则 [2, 3] 之和一定可以整除5。有了这些知识,就可以建立数组和除以K的余数跟其出现次数之间的映射了,注意由于数组中可能出现负数,而我们并不希望出现负余数,所以先对K余数,然后再加个K,再对K取余数,这样一定可以得到正余数。在声明了 HashMap 后,初始化时要把 0 -> 1 先放进去,原因在后面会讲。同时新建变量 sum,用来保存当前的数组和对K的余数,遍历数组A中的数字 num,根据之前说的,num 先对K取余,然后再加上K,之和再加上 sum,再对K取余。此时将 sum 对映射值加到结果 res 中,这里就有两种情况,一种是 sum 并不存在,这样映射值默认是0,另一种是 sum 存在,则根据之前的规律,一定可以找到相同数目的子数组可以整除K,所以将映射值加入结果 res,同时要将 sum 的映射值自增1。这里解释一下为啥刚开始初始化0的映射值是1,因为若 sum 正好是0了,则当前的数组就是符合的题意的,若0的映射值不是1,则这个数组就无法被加入到结果 res 中,参见代码如下:

解法一:

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int res = 0, sum = 0;
        unordered_map<int, int> m{{0, 1}};
        for (int num : A) {
            sum = (sum + num % K + K) % K;
            res += m[sum];
            ++m[sum];
        }
        return res;
    }
};

由于K的余数个数是确定的,所以也可以用个数组来代替 HashMap,其他的部分没啥区别,解题思想也和上面完全一样,参见代码如下:

解法二:

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int res = 0, sum = 0;
        vector<int> cnt(K);
        cnt[0] = 1;
        for (int num : A) {
            sum = (sum + num % K + K) % K;
            res += cnt[sum];
            ++cnt[sum];
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/974

类似题目:

Subarray Sum Equals K

Make Sum Divisible by P

参考资料:

https://leetcode.com/problems/subarray-sums-divisible-by-k/

https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/217985/JavaC%2B%2BPython-Prefix-Sum

https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/217980/Java-O(N)-with-HashMap-and-prefix-Sum

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation