和可被k整除的子数组

发表于 更新于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，974.Subarray Sums Divisible by K

先看题目描述

题目大意是给定一个整数数组，返回其中元素之和可被K整除子数组的数目，其中子数组要求是非空、连续的

思路和算法

由于这道题涉及求子数组和，很容易就想到使用前缀和来解决 ，

我们令 P[i] = A[0] + A[1] + … + A[i]，那么当我们要求一个子数组和 sum(i, j) = A[i] + … + A[j] 时，可以用 P[j] - P[i -1] 表示(其中(0 < i < j)。因此题目中要求的一段子数组和 sum(i, j) mod K = 0 可以等价为 (P[j] - P[i - 1]) mod K = 0 ,又根据同余定理，(P[j] - P[i - 1]) mod K = 0 可以等价为 P[j] mod K = P[i - 1] mod K

有了这个思路我们便可以开始做题，我们可以对数组A进行遍历，在遍历的同时进行统计，当遍历到第 i 个元素时，统计以 i 结尾的符合条件的子数组个数，遍历的同时进行累加就可得到最终答案，而经过上面的分析我们可以知道 sum(i, j) = 0 与 P[j] mod K = P[i - 1] mod K 是等价的，因此以 i 结尾的符合条件的子数组个数便等于在 P[0]到P[i - 1] 中mod K的值与 P[i] mod K 的值相等的元素出现次数。故我们可以定义一个长度为K的 record 数组，用来记录前缀和mod K的值的出现次数，例：当遍历到第 i 个元素时，record[m] 就表示在 P[0]到P[i - 1] 中mod K的结果为m的元素的出现次数(其中 0 < m < K)。因此我们只需在遍历到第 i 个元素时，累加 record[P[i] mod K] ，遍历完第i个元素时，使 record[P[i] mod K] + 1，将数组遍历完以后，累加结果即为最终答案

注意：考虑到前缀和模 K 等于0的情况，在初始化 record 数组时要令 record[0] = 1。在用不同语言负数取模的值不一定相同，Java中%是求余，题目中取模应用Math.floorMod

实现源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int[] record = new int[K];
        record[0] = 1;
        int count = 0;
        int sum = 0;
        for (int a:A) {
            sum = sum + a;
            int mod = Math.floorMod(sum, K);
            count += record[mod];
            record[mod] += 1;
        }
        return count;
    }
}