给你一个下标从 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
初始理解问题
首先,我们需要明确几个关键概念:
- 子数组:指的是数组中一个连续的非空元素序列。例如,对于数组
[1, 2, 3],[1],[2, 3],[1, 2, 3]都是子数组,但[1, 3]不是,因为它不连续。 - 趣味子数组的定义:
- 对于一个子数组
nums[l..r],我们需要统计在这个子数组中满足nums[i] % modulo == k的索引i的数量,记为cnt。 - 然后,我们需要检查
cnt % modulo == k是否成立。如果成立,那么这个子数组就是“趣味子数组”。
- 对于一个子数组
- 目标:统计数组中所有满足上述条件的子数组的数量。
示例分析
为了更好地理解,让我们通过一个具体的例子来说明。
示例 1:
-
nums = [3, 1, 9, 6],modulo = 3,k = 0首先,我们需要找出所有可能的子数组,然后检查哪些是“趣味子数组”。
- 子数组
[3]:- 满足
nums[0] % 3 == 0的是3 % 3 == 0,所以cnt = 1。 cnt % modulo = 1 % 3 = 1,不等于k = 0,所以不是。
- 满足
- 子数组
[1]:1 % 3 == 1,不等于k = 0,cnt = 0。0 % 3 = 0,等于k,所以是趣味子数组。
- 子数组
[9]:9 % 3 == 0,cnt = 1。1 % 3 = 1,不等于0,不是。
- 子数组
[6]:6 % 3 == 0,cnt = 1。1 % 3 = 1,不等于0,不是。
- 子数组
[3, 1]:3 % 3 == 0,1 % 3 == 1,cnt = 1。1 % 3 = 1,不等于0,不是。
- 子数组
[1, 9]:1 % 3 == 1,9 % 3 == 0,cnt = 1。1 % 3 = 1,不等于0,不是。
- 子数组
[9, 6]:9 % 3 == 0,6 % 3 == 0,cnt = 2。2 % 3 = 2,不等于0,不是。
- 子数组
[3, 1, 9]:3 % 3 == 0,1 % 3 == 1,9 % 3 == 0,cnt = 2。2 % 3 = 2,不等于0,不是。
- 子数组
[1, 9, 6]:1 % 3 == 1,9 % 3 == 0,6 % 3 == 0,cnt = 2。2 % 3 = 2,不等于0,不是。
- 子数组
[3, 1, 9, 6]:3 % 3 == 0,1 % 3 == 1,9 % 3 == 0,6 % 3 == 0,cnt = 3。3 % 3 = 0,等于k,所以是趣味子数组。
综上,趣味子数组有
[1]和[3, 1, 9, 6],共 2 个。 - 子数组
暴力解法
最直观的方法是枚举所有可能的子数组,然后对每个子数组计算
cnt并检查条件。这种方法的时间复杂度是 O(n^2),对于较大的n(如 10^5)会非常慢,无法通过。优化思路
我们需要找到一种更高效的方法来统计满足条件的子数组数量。可以考虑前缀和与哈希表的方法。
-
前缀和思想:
- 首先,我们可以预处理数组,将每个元素
nums[i]转换为1如果nums[i] % modulo == k,否则0。这样,cnt就是子数组中1的数量。 - 然后,我们需要统计子数组的和
S满足S % modulo == k。
- 首先,我们可以预处理数组,将每个元素
-
哈希表优化:
- 使用前缀和数组
prefix,其中prefix[i]表示前i个元素的和(即nums[0..i-1]中满足条件的元素个数)。 - 对于子数组
nums[l..r],其cnt = prefix[r+1] - prefix[l]。 - 我们需要
(prefix[r+1] - prefix[l]) % modulo == k。 - 可以重写为
prefix[r+1] % modulo - prefix[l] % modulo ≡ k (mod modulo)。 - 即
prefix[r+1] % modulo ≡ (prefix[l] % modulo + k) % modulo。 - 因此,我们可以维护一个哈希表,记录
prefix[i] % modulo的出现次数,然后在遍历时查找满足上述等式的prefix[l]的数量。
- 使用前缀和数组
-
具体步骤:
- 初始化
prefix = [0],current_sum = 0,count = 0,prefix_mod_counts = {0: 1}。 - 遍历
nums:- 对于每个
num,如果num % modulo == k,则current_sum += 1。 - 计算
current_mod = current_sum % modulo。 - 我们需要
(current_mod - k) % modulo对应的prefix_mod的数量。 target_mod = (current_mod - k) % modulo。count += prefix_mod_counts.get(target_mod, 0)。- 更新
prefix_mod_counts[current_mod]的计数。
- 对于每个
- 返回
count。
- 初始化
代码实现
根据上述思路,我们可以编写如下代码:
from collections import defaultdict class Solution: def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int: # Convert each number to 1 if nums[i] % modulo == k, else 0 transformed = [1 if num % modulo == k else 0 for num in nums] prefix_mod_counts = defaultdict(int) prefix_mod_counts[0] = 1 # initial prefix sum is 0 current_sum = 0 count = 0 for num in transformed: current_sum += num current_mod = current_sum % modulo # We need (current_mod - k) % modulo target_mod = (current_mod - k) % modulo count += prefix_mod_counts.get(target_mod, 0) # Update the counts for current_mod prefix_mod_counts[current_mod] += 1 return count验证示例
让我们用之前的示例验证:
nums = [3, 1, 9, 6],modulo = 3,k = 0transformed = [1, 0, 1, 1](因为3%3=0,1%3=1,9%3=0,6%3=0,k=0所以1对应0)prefix_mod_counts = {0: 1},current_sum = 0,count = 0- 遍历:
num = 1:current_sum = 1,current_mod = 1 % 3 = 1target_mod = (1 - 0) % 3 = 1count += prefix_mod_counts.get(1, 0) = 0prefix_mod_counts = {0:1, 1:1}
num = 0:current_sum = 1,current_mod = 1 % 3 = 1target_mod = (1 - 0) % 3 = 1count += 1(因为prefix_mod_counts[1] = 1),count = 1prefix_mod_counts = {0:1, 1:2}
- `num =
- 子数组:指的是数组中一个连续的非空元素序列。例如,对于数组
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.