当前位置：首页 > news >正文

《哈希表》K倍区间（解题报告）

news 来源：原创 2025/6/25 23:22:45

文章目录

- 零、题目描述
- 一、算法概述
- 二、算法思路
- 三、代码实现
- 四、算法解释
- 五、复杂度分析

零、题目描述

题目链接：K倍区间
在这里插入图片描述

一、算法概述

计算子数组和能被k整除的子数组数量的算法。通过前缀和与哈希表的结合，高效地统计满足条件的子数组。
需要注意的是，题目要求求的是 k 的非负整数倍，而非整数倍，所以哈希表的值光存储次数是不够的，需要维护一个列表，在枚举到第 i 个元素的时候，在哈希表 hashset[ sum[i]%k ] 的所有列表元素中，统计小于等于 sum[i] 的元素个数进行累加，因为只有小于等于 sum[i] 的值才能保证是非负整数倍。

二、算法思路

前缀和数组：计算数组的前缀和数组sum，其中sum[i]表示前i个元素的和。
哈希表与多重集合：使用哈希表hashset，键为前缀和模k的余数，值为对应的前缀和的多重集合。
余数处理：对于每个前缀和sum[i]，计算其模k的余数s，并处理可能的负数余数情况。
查询与统计：在哈希表中查找余数为s的前缀和集合，并统计其中小于当前前缀和的元素数量，累加到结果中。
更新哈希表：将当前前缀和插入到对应的余数集合中。

三、代码实现

#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;
long long sum[100001];int main()
{int n, k;cin >> n >> k;for(int i = 1; i <= n; ++i) {int x;cin >> x;sum[i] = sum[i-1] + x;}long long ans = 0;unordered_map<int, multiset<long long> > hashset;hashset[0].insert(0);for(int i = 1; i <= n; ++i) {int s = sum[i] % k;s = (s + k) % k;int cnt = distance(hashset[s].begin(),hashset[s].upper_bound(sum[i]));ans += cnt;hashset[s].insert(sum[i]);}cout << ans << endl;return 0;
}

四、算法解释

输入处理：读取数组长度n和除数k，然后读取数组元素并计算前缀和数组。
初始化：初始化结果变量ans为0，并在哈希表中插入初始值(0, 0)，处理空数组的情况。
遍历前缀和数组：
- 计算当前前缀和模k的余数s，并处理负数余数。
- 在哈希表中查找余数为s的前缀和集合，统计其中小于当前前缀和的元素数量（注意注意！这题的核心在这里，要求的是非负整数倍，所以必须要找集合中小于当前 sum[i] 的元素值，利用二分去找hashset[s].upper_bound(sum[i])）。
- 将当前前缀和插入到对应的余数集合中。
输出结果：输出满足条件的子数组数量。

五、复杂度分析

时间复杂度：随机数据是 $O (n l o g n)$ 的，如果可以构造数据，会达到 $O(n^2)$ ，本题数据较弱。
空间复杂度： $O (n)$ 。主要用于存储前缀和数组和哈希表。