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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：
思路一：

此题目跟 560 题 非常类似。 我们同样先采用暴力法两层循环去解决问题。

  • // 暴力法
  • // 两层循环
  • // 思路简单，从头开始遍历, i表示 子数组的开始位置，j表示 子数组的结束位置
  • // 当和对 k 取余 == 0, result++
  • // 最终返回 result
  • // 时间复杂度 : O(N ^ 2), 其中N为数组的长度
  • // 空间复杂度 : O(1)
  • // 代码逻辑没问题， 但是提交后， 超时了
  • // 时间复杂度太高

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    public int subarraysDivByK1(int[] A, int K) {

        int result = 0;
        for (int i = 0; i < A.length; i++) {
            int n1 = A[i];
            if (n1 % K == 0) result++;

            for (int j = i + 1; j < A.length; j++) {
                int n2 = A[j];
                if (n1 + n2 % K == 0) {
                    result ++;
                }
                n1 += n2;
            }
        }
        return result;
    }

屏幕快照 2020-05-27 上午11.02.47

利用前序和 ， 哈希表优化

  • 前序和，是指从数组第0项，到数组当前项的总和

  • 如果用数组 prefixsum 表示

  • prefixsum[i] 为数组 第0项，到数组第 i 项的总和

  • 所以 nums 第 i 项到 第 j 项的总和为 prefixsum[j] - prefixsum[i - 1]

  • 题目等价交换

  • 有几种i, j组合，使得 nums[i] 累加到 nums[j] 的总和为 k

  • 有几种i, j组合，使得 prefixsum[j] - prefixsum[i -1] == k

  • 引入哈希表

  • 哈希表中存放 <前序和 ：出现次数>

  • 当遍历到数组某一位置时，如果其前序和 与 K的差值，在哈希表中存在

  • 则次数 += map.get(前序和 - 差值)

  • map中赋值当前前序和，如果之前有，则+1, 没有则赋值1

  • 时间复杂度 O(N)

  • 空间复杂度 O(N)

  • 上述是 题目 560 的解题步骤

  • 974 与 560的不同之处在于 取模

  • (P[j] - P[i]) % k == 0

  • 根据同余定理 P[j] % K == P[i] % K;

  • 所以本题中，字典存放 <前序和 % K, 出现次数>

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public static int subarraysDivByK(int[] A, int K) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int prev = 0, count = 0;
        for (int i = 0; i < A.length; i++) {
            prev += A[i];

            // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = prev % K;
            if (map.containsKey(modulus))
                count += map.get(modulus);
            map.put(modulus, map.getOrDefault(modulus, 0) + 1);
        }
        return count;
    }

时间复杂度 : O(N). 遍历了一遍数组，其中N为数组中元素的个数

空间复杂度: O(N). 额外使用了hashmap内存空间image-20200527143420984