leetcode974. 和可被 K 整除的子数组-前缀和解法

leetcode974. 和可被 K 整除的子数组-前缀和解法

六月 26, 2020

leetcode974. 和可被 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

前缀和

感觉有一点明白前缀和了。这种连续数组的题都可以联想到前缀和，特点是每一个前缀和都有相同的状态。
[0,i]的数组满足对K取模为v，如果这之前的数组也存在一个对K取模为v的，那么这个数就能被K整除。
记录数组的情况用一个map即可。

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) {
        HashMap<Integer,Integer> map = new HashMap<>(1024);
        int count = 0;
        int sum = 0;
        map.put(0,1);//当前sum就能被K整除的情况
        int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            int mod = (sum %K + K) % K;//sum是负数，需要把它变为正数，abs是不对的
            int v = map.getOrDefault(mod,0);
            count += v;
            map.put(mod,v + 1);
        }
        return count;
    }
}

leetcode 106