调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

给你一个下标从 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
通过次数
5.4K
提交次数
14.1K
通过率
38.0%


相关企业

提示 1
The problem can be solved using prefix sums.

提示 2
Let count[i] be the number of indices where nums[i] % modulo == k among the first i indices.

提示 3
count[0] = 0 and count[i] = count[i - 1] + (nums[i - 1] % modulo == k ? 1 : 0) for i = 1, 2, ..., n.

提示 4
Now we want to calculate for each i = 1, 2, ..., n, how many indices j < i such that (count[i] - count[j]) % modulo == k.

提示 5
Rewriting (count[i] - count[j]) % modulo == k becomes count[j] = (count[i] + modulo - k) % modulo.

提示 6
Using a map data structure, for each i = 0, 1, 2, ..., n, we just sum up all map[(count[i] + modulo - k) % modulo] before increasing map[count[i] % modulo], and the total sum is the final answer.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
nums =
[3,2,4]
modulo =
2
k =
1
Source