点击获取AI摘要

2845. 统计趣味子数组的数目 M

给你一个下标从 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

问题分析

我们要统计子数组中满足以下两个条件的子数组个数：

在子数组范围内，满足 nums[i] % modulo == k 的元素个数记为 cnt
且 cnt % modulo == k

算法思路

为了更方便地计数，我们先把原数组 nums 转换成一个二值数组 b：
1
b[i] = 1 if nums[i] % modulo == k else 0
此时，任意子数组 [l..r] 中满足条件的元素个数

就是 b[l] + b[l+1] + … + b[r]。
引入前缀和 + 模运算

定义前缀和数组 P，并对 modulo 取模，使得计算更简单：
1
2
P[0] = 0
P[i] = (b[0] + b[1] + … + b[i-1]) % modulo （1 ≤ i ≤ n）
- 注意：P[i] 表示前 i 个元素（即 b[0..i-1]）的和 mod modulo
那么子数组 [l..r] 的“有趣计数” cnt = b[l] + … + b[r]，可以写成：
1
cnt = (P[r+1] - P[l] + modulo) % modulo
我们需要 cnt % modulo == k，即
1
2
3
(P[r+1] - P[l]) % modulo == k
⇔ P[r+1] ≡ P[l] + k (modulo)
⇔ P[l] ≡ P[r+1] - k (modulo)
利用哈希表计数

由上面等式可知：在遍历到位置 r（即计算出 P[r+1]）时，我们只要知道有多少个 l < r+1 使得

$P[l] \equiv (P[r+1] - k) \bmod \text{modulo}$

即可将这些子数组都计入答案。因此，我们用一个哈希表 cntMap 来维护“每种前缀和出现的次数”：
- 键：某个值 v 表示前缀和 P[*] = v
- 值：该前缀和出现了多少次

时间复杂度

时间复杂度：

遍历一次数组，共 n 步
每步中哈希表的查询与更新均摊 O(1) → 总体 O(n)

空间复杂度：哈希表 cntMap 最多存储 O(min(n, modulo)) 个不同的前缀和值 → 最坏 O(n)，通常远小于 n

代码分解

初始化
1
2
3
4
cntMap = defaultdict(int)
cntMap[0] = 1
cur = 0 # 当前前缀和 P[i]（初始化为 P[0]）
ans = 0
- cntMap[0] = 1：表示空前缀（即 P[0]）出现 1 次，便于统计以开头就满足条件的子数组

遍历数组

对于每个 x = nums[i]，更新：

1
2
3

if x % modulo == k:
    cur = (cur + 1) % modulo
# 此时 cur = P[i+1]

查询并累加

计算目标前缀和值：
1
2
target = (cur - k + modulo) % modulo
ans += cntMap[target]
这一步相当于“找到所有 l，使得 P[l] == target”，将其数量直接加到答案中
更新哈希表
1
cntMap[cur] += 1
将当前前缀和也记入哈希表，以便后续作为 l 被使用

遍历结束后，ans 即为所有“趣味子数组”的总数

代码实现

from collections import defaultdict
from typing import List

class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        # b[i] = 1 if nums[i] % modulo == k else 0
        # 前缀和计数映射
        cntMap = defaultdict(int)
        cntMap[0] = 1    # 初始：空前缀和为 0 出现过一次
        
        cur = 0          # 当前前缀和（modulo 取模后）
        ans = 0
        
        for x in nums:
            # 转换 b[i] 并更新前缀和
            if x % modulo == k:
                cur = (cur + 1) % modulo
            
            # 计算能与当前前缀和配对的目标值
            target = (cur - k + modulo) % modulo
            ans += cntMap[target]
            
            # 记录当前前缀和出现次数
            cntMap[cur] += 1
        
        return ans

以 nums = [3,2,4]，modulo = 2，k = 1 为例：

i	nums[i]	nums[i]%2==1?	b[i]	cur (P[i+1])	target=(cur−k)%2	cntMap before	新增 ans	cntMap after
初始				cur = 0		{0:1}	0	{0:1}
i=0	3	是	1	(0+1)%2 = 1	(1-1)%2 = 0	{0:1}	+1 → 1	{0:1, 1:1}
i=1	2	否	0	(1+0)%2 = 1	(1-1)%2 = 0	{0:1,1:1}	+1 → 2	{0:1, 1:2}
i=2	4	否	0	(1+0)%2 = 1	(1-1)%2 = 0	{0:1,1:2}	+1 → 3	{0:1, 1:3}

i=0：cur=1，target=0，cntMap[0]=1，ans=1
i=1：cur=1，target=0，cntMap[0]=1，ans=2
i=2：cur=1，target=0，cntMap[0]=1，ans=3