[LeetCode] 974. Subarray Sums Divisible by K

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)