题目链接直达

1. 题目描述

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

• 1 <= nums[i] <= 10⁹

• 1 <= modulo <= 10⁹

• 0 <= k < modulo

2. 分析

核心思路：前缀和+哈希表。

分析：

1. 数据转化：nums[i] % modulo == k，贡献值为1；nums[i]%modulo!=k，贡献值为0。转化为求解：元素和%modulo==k的子数组的数量。

2. 针对元素和%modulo==k的子数组的数量求解，可以进行如下分析：

对于子数组 sum[l:r] = sum[r] - sum[l-1]

sum[l:r] % modulo == k

=> (sum[r] - sum[l-1]) % modulo == k % modulo

(sum[r] - sum[l-1] - k + sum[l-1]) % modulo == (k - k + sum[l-1])%modulo

=>

(sum[r] - k) % modulo == sum[l-1] % modulo

参考求解区间和为k的子数组，我们只需要记录前缀数，即可。

3. 代码

func countInterestingSubarrays(nums []int, modulo int, k int) int64 {
    // 1. 转化为贡献值
    for i, v := range nums {
        if v%modulo == k {
            nums[i] = 1
        } else {
            nums[i] = 0
        }
    }
    // 2. 转化为求解 元素和%modulo==k的子数组
    cnt := map[int]int{}
    cnt[0] = 1
    sum := 0
    ans := 0
    for _, v := range nums {
        // (sum[r] - k) % modulo == sum[l-1] % modulo
        sum += v
        ans += cnt[(sum-k)%modulo]
        cnt[sum%modulo]++
    }
    return int64(ans)
}

优化：上述贡献值转化，可以进一步在前缀和累加过程去做

func countInterestingSubarrays(nums []int, modulo int, k int) int64 {
    cnt := map[int]int{}
    cnt[0] = 1
    sum := 0
    ans := 0
    for _, v := range nums {
        if v % modulo == k {
            sum++
        }
        ans += cnt[(sum-k)%modulo]
        cnt[sum%modulo]++
    }
    return int64(ans)
}