Keshawn_lu's Blog

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

哈希表
字数统计: 498阅读时长: 2 min
2020/05/27 Share

题目简介：

给定一个整数数组 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

思路：

使用前缀和的思想，sum[i]代表以i为结尾的前缀和，若数组[i, ……, j]元素之和能被 K 整除，则(sum[j] - sum[i - 1]) % K == 0，根据同余定理，可以得到sum[j] % K == sum[i - 1] % K，所以我们将每次数组元素和除 K 的余数存入哈希表，并在遍历时判断之前有没有相同的余数，若有，则中间的一段数组便满足要求。

因为C++取模时，当被除数为负数时取模结果为负数(如 -1 % 2 == -1, 但是2 == -1 * -1 + 1，所以正确结果为1)，所以求余数时需要用(sum % K + K) % K的形式。

相当于给所有的前缀和一个偏移量 K，正数取模不变，负数取模变成 K 加这个负数。

tips:

  • 哈希表中余数为0需赋初值1，例如sum = 3, K = 3, sum % K == 0，如果不赋初值，则这个数组无法被统计到。

  • 前缀和：一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

  • 同余定理：如果两个整数的差（a-b）能被m整除，那么a，b对m同余，即余数相同。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {

        unordered_map<int, int> record = {{0, 1}};

        int sum = 0;
        int count = 0;
        for(int i = 0; i < A.size(); i++){

            sum +=  A[i];
            int mod_res = (sum % K + K) % K;    //防止sum为负数时出错

            if(record.count(mod_res)){
                count += record[mod_res];
            }

            record[mod_res]++;
        }

        return count;

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网