1. 题目描述
给你一个下标从 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 <= 105
1 <= nums[i] <= 109
1 <= modulo <= 109
0 <= k < modulo
2. 分析
核心思路:前缀和+哈希表。
分析:
数据转化:nums[i] % modulo == k,贡献值为1;nums[i]%modulo!=k,贡献值为0。转化为求解:元素和%modulo==k的子数组的数量。
针对元素和%modulo==k的子数组的数量求解,可以进行如下分析:
对于子数组 sum[l:r] = sum[r] - sum[l-1]
sum[l:r] % modulo == k
=> (sum[r] - sum[l-1]) % modulo == k % modulo
(sum[r] - sum[l-1] - k + sum[l-1]) % modulo == (k - k + sum[l-1])%modulo
=>
(sum[r] - k) % modulo == sum[l-1] % modulo
参考求解区间和为k的子数组,我们只需要记录前缀数,即可。
3. 代码
func countInterestingSubarrays(nums []int, modulo int, k int) int64 {
// 1. 转化为贡献值
for i, v := range nums {
if v%modulo == k {
nums[i] = 1
} else {
nums[i] = 0
}
}
// 2. 转化为求解 元素和%modulo==k的子数组
cnt := map[int]int{}
cnt[0] = 1
sum := 0
ans := 0
for _, v := range nums {
// (sum[r] - k) % modulo == sum[l-1] % modulo
sum += v
ans += cnt[(sum-k)%modulo]
cnt[sum%modulo]++
}
return int64(ans)
}
优化:上述贡献值转化,可以进一步在前缀和累加过程去做
func countInterestingSubarrays(nums []int, modulo int, k int) int64 {
cnt := map[int]int{}
cnt[0] = 1
sum := 0
ans := 0
for _, v := range nums {
if v % modulo == k {
sum++
}
ans += cnt[(sum-k)%modulo]
cnt[sum%modulo]++
}
return int64(ans)
}
评论