统计趣味子数组的数目
难度:
标签:
题目描述
You are given a 0-indexed integer array nums, an integer modulo, and an integer k.
Your task is to find the count of subarrays that are interesting.
A subarray nums[l..r] is interesting if the following condition holds:
- Let
cntbe the number of indicesiin the range[l, r]such thatnums[i] % modulo == k. Then,cnt % modulo == k.
Return an integer denoting the count of interesting subarrays.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [3,2,4], modulo = 2, k = 1 Output: 3 Explanation: In this example the interesting subarrays are: The subarray nums[0..0] which is [3]. - There is only one index, i = 0, in the range [0, 0] that satisfies nums[i] % modulo == k. - Hence, cnt = 1 and cnt % modulo == k. The subarray nums[0..1] which is [3,2]. - There is only one index, i = 0, in the range [0, 1] that satisfies nums[i] % modulo == k. - Hence, cnt = 1 and cnt % modulo == k. The subarray nums[0..2] which is [3,2,4]. - There is only one index, i = 0, in the range [0, 2] that satisfies nums[i] % modulo == k. - Hence, cnt = 1 and cnt % modulo == k. It can be shown that there are no other interesting subarrays. So, the answer is 3.
Example 2:
Input: nums = [3,1,9,6], modulo = 3, k = 0 Output: 2 Explanation: In this example the interesting subarrays are: The subarray nums[0..3] which is [3,1,9,6]. - There are three indices, i = 0, 2, 3, in the range [0, 3] that satisfy nums[i] % modulo == k. - Hence, cnt = 3 and cnt % modulo == k. The subarray nums[1..1] which is [1]. - There is no index, i, in the range [1, 1] that satisfies nums[i] % modulo == k. - Hence, cnt = 0 and cnt % modulo == k. It can be shown that there are no other interesting subarrays. So, the answer is 2.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= modulo <= 1090 <= k < modulo
代码结果
运行时间: 136 ms, 内存: 29.7 MB
// 思路：
// 1. 使用流处理来生成所有子数组。
// 2. 对每个子数组计算满足 nums[i] % modulo == k 的元素个数 cnt。
// 3. 通过流的 filter 操作过滤出 cnt % modulo == k 的子数组并统计其数量。
import java.util.stream.IntStream;
public class Solution {
public long countInterestingSubarrays(int[] nums, int modulo, int k) {
return IntStream.range(0, nums.length)
.flatMap(start -> IntStream.range(start, nums.length)
.map(end -> (int) IntStream.range(start, end + 1)
.filter(i -> nums[i] % modulo == k)
.count()))
.filter(cnt -> cnt % modulo == k)
.count();
}
}解释
方法:
题解采用了前缀和和哈希表的思想。首先，遍历数组，计算出以每个元素为结尾的子数组中满足条件 nums[i] % modulo == k 的元素个数的累计和 temp。然后，计算出满足条件的子数组的个数。为了避免重复计算，使用哈希表 mp 来存储每个可能的累计和出现的次数。对于每个元素，我们计算出在当前累计和下，满足 cnt % modulo == k 的累计和 sl，然后将哈希表中对应 sl 的值累加到结果 res 中。最后，更新哈希表中当前累计和的计数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中，为什么使用前缀和的方法来统计满足条件的子数组，而不是直接枚举所有可能的子数组？
▷🦆
哈希表中键值对的含义是什么？具体来说，哈希表中的键和值分别代表了什么？
▷🦆
在更新哈希表 `mp[temp] += 1` 时，这一操作的目的是什么？
▷🦆
如何理解计算 `sl = (temp - k + modulo) % modulo` 的逻辑？这一步骤是如何帮助我们找到满足条件的子数组的？
▷