今日学习记录
1. 3729. 统计有序数组中可被 K 整除的子数组数量
关键词：前缀和 同余 哈希表
问题分析：
找到给定数组的子数组,该子数组满足可以被 k 整除,但是不能重复选取相同的子数组
数组是不严格单调递增的!!!
核心思路:
要找到符合条件的子数组很简单,先看一个式子推导
(pre[r] - pre[l])%k = 0->pre[r]%k = pre[l]%k
即就是要找到前缀和数组中对 k 取余之后相等的两个数,进行匹配,使用哈希表技巧(枚举右,维护左)
但是问题来了,怎么去重?
我们遇到的难点无疑就是对整个选中的数组进行去重,难道真的直接储存吗,显然是不可能的
(不清楚进制哈希可以跳过了)
但是我们根据哈希表存储的规则可以想到,可以设置一个哈希函数,用来计算不同数组的哈希值是否相同,以此判断数组相同,这显然是不行的,先不说答案是 long long 类型的,不可能要存这么多,而且这个哈希函数太难写了,数组中的数据范围为 0~1e9,分布太离散,我们即使使用 64 位的大质数也无法使数据有更好的分布,所以这个方法不行
我们似乎还有一个条件没用到,那就是单调性,这个单调性实际上把数组分为 m 个不同的区段,区段中的数据都是相同的
所以我们先来搞清楚为什么会重复,例如在取模后的前缀和数组nums=[1,2,1,1,1,3]中
枚举右的时候与左边的进行匹配时会产生相同的数组,而我们的数组中为 m 个不同的区段,我们可以一个区段一个区段的解决,在数据相同的区段中,我们只需要找到长度不同的数组就行,但是哈希表技巧不能改,不然我们无法与前面的区段匹配,我们可以先不计算该区段的值,在遇到下一个不同区段时,再计算区段中的值,换句话说,对于连续相同元素段,我们要保证哈希表暂时不包含这一段对应的前缀和,等遍历完这一段,再把对应的前缀和加到哈希表中.
**最终代码：
long long numGoodSubarrays(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int,int> mp;
mp[0] = 1;
long long ans = 0,sum = 0;
int pos = 0;
for(int i = 0;i<n;i++){
int x = nums[i];
if(i>0&&x!=nums[i-1]){
long long s= sum;
for(int j = i-1;j>=pos;j--){
mp[s%k]++;
s -= nums[i-1];
}
pos = i;
}
sum += x;
ans += mp[sum%k];
}
return ans;
}学到的点：
- 哈希表中去重的技巧