给你一个下标从 0 开始的整数数组 nums ,以及整数 modulo 和整数 k 。 请你找出并统计数组中 趣味子数组 的数目。 如果 子数组 nums[l..r]…
- User
给你一个下标从 0 开始的整数数组 nums ,以及整数 modulo 和整数 k 。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 nums[l..r] 满足下述条件,则称其为 趣味子数组 :
在范围 [l, r] 内,设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。 以整数形式表示并返回趣味子数组的数目。
注意:子数组是数组中的一个连续非空的元素序列。
class Solution: def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
- Assistant
我们可以利用前缀和的思想来解决这个问题。记下前缀和数组 ( P ) 其中
[ P[i+1] = P[i] + \mathbf{1}{,nums[i] % modulo == k,} ]
其中 (\mathbf{1}{\cdot}) 表示判断是否满足条件,满足为 1,否则为 0。那么区间 ([l,r]) 内满足条件的元素个数为 [ cnt = P[r+1] - P[l] ] 题目要求 [ cnt % modulo == k ] 利用模运算的性质,上式等价于 [ (P[r+1] - P[l]) % modulo == k \quad\Longleftrightarrow\quad P[r+1] % modulo == (P[l] + k) % modulo ]
因此对于每个前缀 ( P[j] ) (其中 ( j = r+1 )),我们希望统计有多少个 ( i ) (对应 ( l )),使得 [ P[i] \equiv P[j]-k ; (\bmod; modulo). ] 我们可以边遍历数组边统计前缀模值的出现次数,从而在 ( O(n) ) 时间内求出答案。
下面给出完整的代码实现:
class Solution: def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int: # freq 用来记录前缀 P[i] (i 从 0 到 n) 的模 modulo 的值出现的次数 freq = {0: 1} # 初始时 P[0] = 0 prefix = 0 # 当前前缀和(计数) res = 0 for num in nums: # 如果当前数字满足条件,则累加 1 if num % modulo == k: prefix += 1 # 当前前缀模 modulo 的值 cur_mod = prefix % modulo # 如果存在之前的前缀使得: prior_mod = (cur_mod - k) % modulo,则 [l, r] 便是合法子数组 need_mod = (cur_mod - k) % modulo res += freq.get(need_mod, 0) # 更新 freq freq[cur_mod] = freq.get(cur_mod, 0) + 1 return res
说明
- 前缀定义:我们定义
prefix为当前前缀中满足nums[i] % modulo == k的元素个数。 - 子数组与前缀差:对于子数组
[l, r],其“计数”即为 ( P[r+1]-P[l] )。因此要求 ((P[r+1]-P[l]) % modulo == k),这可以转换为 ( P[r+1] % modulo == (P[l] + k) % modulo )。 - 计数方法:遍历数组时,我们统计每个前缀模值出现的次数,对于当前前缀
cur_mod,只需要找到之前出现次数中,模值等于 ((cur_mod - k) % modulo) 的个数即可。这些配对的前缀组合对应一个合法的子数组。 - 边界:初始时
freq={0:1}对应空前缀 (P[0]=0);这样当子数组从数组起始位置开始时也能正确计数。
这种方法能够在线性时间内统计所有满足条件的子数组。
- 前缀定义:我们定义
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.