LeetCode 题解工作台
统计趣味子数组的数目
给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。 请你找出并统计数组中 趣味子数组 的数目。 如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ： 在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
题目要求一个区间内满足 $nums[i] \bmod modulo = k$ 的索引 的数量，我们可以将数组 转换为一个 数组 ，其中 $arr[i] = 1$ 表示 $nums[i] \bmod modulo = k$，否则 $arr[i] = 0$。 那么对于一个区间 $[l, r]$，我们可以通过前缀和数组 来计算 中 的数量，即 $s[r] - s[l - 1]$，其中 $s[…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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 <= 1051 <= nums[i] <= 1091 <= modulo <= 1090 <= k < modulo
解题思路
方法一：哈希表 + 前缀和
题目要求一个区间内满足 的索引 的数量，我们可以将数组 转换为一个 数组 ，其中 表示 ，否则 。
那么对于一个区间 ，我们可以通过前缀和数组 来计算 中 的数量，即 ，其中 。
我们用哈希表 记录前缀和 出现的次数，初始时 。
接下来，我们遍历数组 ，计算前缀和 ，将 出现的次数累加到答案中，然后将 出现的次数加 。
遍历结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
arr = [int(x % modulo == k) for x in nums]
cnt = Counter()
cnt[0] = 1
ans = s = 0
for x in arr:
s += x
ans += cnt[(s - k) % modulo]
cnt[s % modulo] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is processed once. Space complexity is O(min(n, modulo)) since the hash map stores counts of prefix sums modulo modulo, limited by the smaller of array length or modulo. |
| 空间 | O(\min(n, \textit{modulo})) |
面试官常问的追问
外企场景- question_mark
You are expected to identify that brute force checking of all subarrays is too slow for large arrays.
- question_mark
Look for the connection between counting elements satisfying a modulo condition and prefix sums.
- question_mark
Using a hash map to track prefix sum frequencies is a strong hint for an efficient solution.
常见陷阱
外企场景- error
Forgetting to transform the array to a 0/1 count based on the modulo condition, which breaks prefix sum logic.
- error
Incorrectly computing prefix sum differences modulo the given value, leading to wrong subarray counts.
- error
Not initializing the hash map with the base case prefix sum of 0, which misses subarrays starting at index 0.
进阶变体
外企场景- arrow_right_alt
Count subarrays where the sum of elements modulo a given number equals k instead of counting individual indices.
- arrow_right_alt
Handle arrays with negative numbers where modulo operation behaves differently, requiring adjustment in prefix sums.
- arrow_right_alt
Find the longest interesting subarray instead of counting all subarrays, adapting the same prefix sum plus hash map technique.