leetcode 974. Subarray Sums Divisible by K 解题思路分析

题目大意：

和可被 K 整除的子数组

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

示例：

输入：A = [4,5,0,-2,-3,1], K = 5 
输出：7 
解释： 有 7 个子数组满足其元素之和可被 K = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] 

提示：

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=974

解题思路：

这道题最早是用动态规划DP来做的，结果提交后超时了。后来想到了余数的一个特性，才恍然大悟！首先简单说下余数的这个特性，如果任意两个数字除以K得到的余数相同，那么两数之差一定可以被K整除。举个例子：

int a = 7;
int b = 12;
int K = 5;

// 因为
a % K = 7 % 5 = 2;
b % K = 12 % 5 = 2;

// 所以
(b - a) % K = (12 - 7) % 5 = 0;

这是一个简单的数学定理，在这就不必展开讨论。那么如果来运用这个定理解开本题呢？

首先，对于数组任意一个连续子数组的和sum[i1, i2](下标i1到i2之和)应该等于：

sum[i1, i2] = sum[0, i2] - sum[0, i1];

也就是说，只要我们求出下列子数组的和，

sum[0, 0];
sum[0, 1];
sum[0, 2];
...
sum[0, n];

那么对于数组中任意一个区间的和，都可以由上面相应的2个sum之差来取得。另外，根据上面提到的余数定理，所有sum分别除以K，余数相同的sum之差是可以被K整除的，所以问题就转化为，寻找余数相同的个数。

我们定义一个Map来存储每个余数对应的个数：

Map<Integer, Integer> countMap = new HashMap<>();

举个例子，比如当前countMap中余数为1的个数是5，当我们又找到一个sum%K的余数为1时，由于当前sum与之前5个的差都可以被K整除，所以结果会增加5。此外还要注意一个问题，当余数为0时，当前sum本身也是一个解，别忘了加入结果中。

最后还有一个小坑需要注意一下，在java语言中，负数与正整数的余为负数，所以需要特别转换下。比如：

-3 % 5 = -3;

我们应该将其转换为正数：

-3 % 5 + 5 = 2;

最后看下完整的代码：

public int subarraysDivByK(int[] A, int K) {
    int count = 0; // 返回结果
    Map<Integer, Integer> countMap = new HashMap<>(); // 记录相同余数个数的map
    int sum = 0;
    // 循环数组A，分别求出sum[0,1],sum[0,2]到sum[0,n]
    for (int a : A) {
        sum += a;
        // 当前sum的余数
        int rem = sum % K;
        // 如果余数小于0，转化为正数
        if (rem < 0) {
            rem = rem + K;
        }
        // 如果余数为0，当前sum区间即是一个结果
        if (rem == 0) {
            count++;
        }
        // 从map中取得之前相同余数的个数
        int countOfMod = countMap.getOrDefault(rem, 0);
        // 将个数加入到结果中
        count = count + countOfMod;
        // 更新map中该余数的个数
        countMap.put(rem, ++countOfMod);
    }
    return count;
}

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-974-subarray-sums-divisible-by-k-解题思路分析/