2845. 统计趣味子数组的数目
给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：
在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。
以整数形式表示并返回趣味子数组的数目。
注意：子数组是数组中的一个连续非空的元素序列。
示例 1：
输入：nums = [3,2,4], modulo = 2, k = 1
输出：3
解释：在这个示例中，趣味子数组分别是：
子数组 nums[0..0] ，也就是 [3] 。
- 在范围 [0, 0] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..1] ，也就是 [3,2] 。 - 在范围 [0, 1] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..2] ，也就是 [3,2,4] 。 - 在范围 [0, 2] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组。因此，答案为 3 。
示例 2：
输入：nums = [3,1,9,6], modulo = 3, k = 0
输出：2
解释：在这个示例中，趣味子数组分别是：
子数组 nums[0..3] ，也就是 [3,1,9,6] 。
- 在范围 [0, 3] 内，只存在 3 个下标 i = 0, 2, 3 满足 nums[i] % modulo == k 。
- 因此 cnt = 3 ，且 cnt % modulo == k 。
子数组 nums[1..1] ，也就是 [1] 。 - 在范围 [1, 1] 内，不存在下标满足 nums[i] % modulo == k 。
- 因此 cnt = 0 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组，因此答案为 2 。
提示：
\[1 <= nums.length <= 10^5\\
1 <= nums[i] <= 10^9\\
1 <= modulo <= 10^9\\
0 <= k < modulo\\
\]
解题思路：
见代码注释
code
class Solution {
public:
/*
综合考察以下内容：前缀和 + 哈希表 + 数学
1. 问题转换 -> 前缀和
nums[l,r]中nums[i] % m == k 的元素的数目cnt;
如何快速查询num[l,r]之间的cnt?前缀和
区间查询：前缀和
区间更新：差分
止步于此：如果遍历所有的区间的时间复杂度依然是O(n ^ 2)
2.两数之和 -> 哈希表
其实进一步思考得写出前缀和计算公式
前缀和需要在最前面补上一个0,那么nums[l,r]之间的和为：
prefix[r + 1] - prefix[l]
那么最后需要判断的就是：
(prefix[r + 1] - prefix[l]) % m == k
也就是需要判断：
prefix[r + 1] % m - prefix[l] % m == k
那这样就简单了：两数之和，通过哈希表进行查找：
已经知道右端点的值：prefix[r+1] - k,那么自然是在哈希表中查找prefix[l] % m
3. 公式变形
但是存在得到一个问题是：
6 % 3 - 2 % 3 = -2
(6 - 2) % 3 = 1
大小关系发生了变化
也就是实际上得有两种情况：负数补上一个m
(x - y) % 3 = x % 3 - y % 3
(x - y) % 3 = x % 3 - y % 3 + 3
综合起来就是：
不需要补上m:
prefix[r + 1] % m - prefix[l] % m = k
prefix[r + 1] % m - k = prefix[l] % m
需要补上m:
prefix[r + 1] % m - prefix[l] % m + m = k
prefix[r + 1] % m - k + m = prefix[l] % m
综合起来就是：
(prefix[r + 1] % m - k + m) % m = prefix[l] % m
综合的公式有点没太看懂，但是不综合起来也没什么问题，无非就是判断以下最终的结果负与非负罢了。
公式推导曲折多变，不熟的话怎么能在有限紧张的时间里面写出来呢？
接下来就简单：遍历右端点，通过哈希表查询左端点的数目。
*/
long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
int len = nums.size();
vector<int> prefix(len + 1,0);
for(int i = 0;i < nums.size();i ++)
{
if(nums[i] % modulo == k) prefix[i+1] = (prefix[i] + 1) % modulo;
else prefix[i+1] = prefix[i];
}
long long int ans = 0;
unordered_map<int,int> cnt;
cnt[0] = 1;
for(int right = 1;right < prefix.size();right ++)
{
int target = (prefix[right] - k + modulo) % modulo;
auto it = cnt.find(target);
if(it != cnt.end())
{
ans += it -> second;
}
cnt[prefix[right]] ++;
}
return ans;
}
};
class Solution {
public:
//优化掉前缀和数组
long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
int len = nums.size();
//vector<int> prefix(len + 1,0);
//for(int i = 0;i < nums.size();i ++)
//{
// if(nums[i] % modulo == k) prefix[i+1] = (prefix[i] + 1) % modulo;
// else prefix[i+1] = prefix[i];
//}
long long int ans = 0;
unordered_map<int,int> cnt;
cnt[0] = 1;
int prefix = 0;
for(int i = 0;i < len;i ++)
{
if(nums[i] % modulo == k) prefix = (prefix + 1) % modulo;
int target = (prefix - k + modulo) % modulo;
auto it = cnt.find(target);
if(it != cnt.end())
{
ans += it -> second;
}
cnt[prefix] ++;
}
return ans;
}
};