echo

任生命穿梭 时间的角落

0%

和可被 K 整除的子数组

Posted on In Valine:

974. 和可被 K 整除的子数组

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

示例：

1
2
3
4
5
输入：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

暴力解法：使用两个循环枚举子数组的起点和终点，统计子数组的和并判断是否整除 k 。时间复杂度 O(n^3) 空间复杂度 O(1)。

暴力解法优化：使用一个数组存储前缀和 p[i] 表示[0…i]的数字之和，p[j] - p[i] 表示一个子数组的和。时间复杂度 O(n^2) 空间复杂度 O(n)。

哈希表：使用哈希表存储，以前缀和模 K 的值为键，其值出现的次数为值。在遍历数组的同时更新。我们需要对哈希表初始化，即余数为 0 出现的次数为 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> record = new HashMap<>();
        int sum = 0, ans = 0;
        //初始化
        record.put(0,1);
        for(int e : A){
            sum += e;
            //Java 负数取模产生负数，需要纠正
            int mod = (sum % K + K) % K;
            //得到前缀和模 K 的值出现的次数
            int times = record.getOrDefault(mod, 0);
            //更新结果和以 mod 为余数的前缀和出现的次数
            ans += times;
            record.put(mod, times + 1);
        }
        return ans;
    }
}

时间复杂度 O(n) 遍历一次数组，空间复杂度 O( min (n, k) ) 模 k 得到的余数最多有 k 个。

我们还可以先生成哈希表，得到前缀和模 k 的值出现的次数 n，对于这个值，和可被 k 整除的子数组的个数为 n(n-1)/2，类似于冒泡排序的两两比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> record = new HashMap<>();
        int sum = 0, ans = 0;
        record.put(0,1);
        for(int e : A){
            sum += e;
            //Java 负数取模产生负数，需要纠正
            int mod = (sum % K + K) % K;
            record.put(mod, record.getOrDefault(mod, 0) + 1);
        }
        for(Map.Entry<Integer, Integer> entry : record.entrySet()){
            ans += entry.getValue() * (entry.getValue() - 1) / 2;
        }
        return ans;
    }
}

时间复杂度和空间复杂度同上。