X

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-解题思路分析/
Categories: leetcode
admin: