Medium

题目描述

给你一个下标从 0 开始的整数数组 nums，一个整数 modulo 和一个整数 k。

你的任务是找到有趣子数组的数量。

如果子数组 nums[l..r] 满足以下条件，则称为有趣的：

设 cnt 为范围 [l, r] 中满足 nums[i] % modulo == k 的下标 i 的数量。那么 cnt % modulo == k。

返回一个表示有趣子数组数量的整数。

注意：子数组是数组中连续的非空元素序列。

示例 1：

输入：nums = [3,2,4], modulo = 2, k = 1
输出：3
解释：在这个示例中，有趣的子数组有：
子数组 nums[0..0] 即 [3]。
- 在范围 [0, 0] 中只有一个下标 i = 0 满足 nums[i] % modulo == k。
- 因此，cnt = 1 且 cnt % modulo == k。
子数组 nums[0..1] 即 [3,2]。
- 在范围 [0, 1] 中只有一个下标 i = 0 满足 nums[i] % modulo == k。
- 因此，cnt = 1 且 cnt % modulo == k。
子数组 nums[0..2] 即 [3,2,4]。
- 在范围 [0, 2] 中只有一个下标 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] 中有三个下标 i = 0, 2, 3 满足 nums[i] % modulo == k。
- 因此，cnt = 3 且 cnt % modulo == k。
子数组 nums[1..1] 即 [1]。
- 在范围 [1, 1] 中没有下标 i 满足 nums[i] % modulo == k。
- 因此，cnt = 0 且 cnt % modulo == k。
可以证明没有其他有趣的子数组。因此，答案是 2。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= modulo <= 10^9
  • 0 <= k < modulo

解题思路

这是一个经典的前缀和 + 哈希表问题。核心思想是将问题转化为寻找满足条件的前缀和对。

思路分析：

  1. 前缀和预处理：定义 count[i] 为前 i 个元素中满足 nums[j] % modulo == k 的元素个数。

    • count[0] = 0（空前缀）
    • count[i] = count[i-1] + (nums[i-1] % modulo == k ? 1 : 0)

  2. 转化问题：对于子数组 nums[l..r]，其中满足条件的元素个数为 count[r+1] - count[l]。 要求 (count[r+1] - count[l]) % modulo == k。

  3. 数学变换：等式可以重写为： count[l] % modulo == (count[r+1] - k + modulo) % modulo

  4. 哈希表优化：使用哈希表记录每个前缀和模 modulo 的值出现的次数。 对于当前位置 i，查找有多少个位置 j < i 满足 count[j] % modulo == (count[i] - k + modulo) % modulo。

算法流程：

  • 初始化哈希表，cnt_map[0] = 1（空前缀的贡献）
  • 遍历数组，维护前缀和 prefix_count
  • 对于每个位置，先查找符合条件的前缀个数，再更新哈希表

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(min(n, modulo))。

代码实现

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        unordered_map<int, int> cnt_map;
        cnt_map[0] = 1;  // 空前缀
        
        long long result = 0;
        int prefix_count = 0;
        
        for (int num : nums) {
            if (num % modulo == k) {
                prefix_count++;
            }
            
            // 查找满足条件的前缀
            int target = (prefix_count - k + modulo) % modulo;
            if (cnt_map.count(target)) {
                result += cnt_map[target];
            }
            
            // 更新当前前缀的计数
            cnt_map[prefix_count % modulo]++;
        }
        
        return result;
    }
};

class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        from collections import defaultdict
        
        cnt_map = defaultdict(int)
        cnt_map[0] = 1  # 空前缀
        
        result = 0
        prefix_count = 0
        
        for num in nums:
            if num % modulo == k:
                prefix_count += 1
            
            # 查找满足条件的前缀
            target = (prefix_count - k + modulo) % modulo
            result += cnt_map[target]
            
            # 更新当前前缀的计数
            cnt_map[prefix_count % modulo] += 1
        
        return result

public class Solution {
    public long CountInterestingSubarrays(IList<int> nums, int modulo, int k) {
        var cntMap = new Dictionary<int, int>();
        cntMap[0] = 1;  // 空前缀
        
        long result = 0;
        int prefixCount = 0;
        
        foreach (int num in nums) {
            if (num % modulo == k) {
                prefixCount++;
            }
            
            // 查找满足条件的前缀
            int target = (prefixCount - k + modulo) % modulo;
            if (cntMap.ContainsKey(target)) {
                result += cntMap[target];
            }
            
            // 更新当前前缀的计数
            int key = prefixCount % modulo;
            if (cntMap.ContainsKey(key)) {
                cntMap[key]++;
            } else {
                cntMap[key] = 1;
            }
        }
        
        return result;
    }
}

var countInterestingSubarrays = function(nums, modulo, k) {
    const n = nums.length;
    let count = 0;
    let prefixCount = 0;
    const map = new Map();
    map.set(0, 1);
    
    for (let i = 0; i < n; i++) {
        if (nums[i] % modulo === k) {
            prefixCount++;
        }
        
        const remainder = prefixCount % modulo;
        const target = (remainder - k + modulo) % modulo;
        
        if (map.has(target)) {
            count += map.get(target);
        }
        
        map.set(remainder, (map.get(remainder) || 0) + 1);
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(min(n, modulo))

说明：

  • 时间复杂度：只需要遍历数组一次，每次哈希表操作为 O(1)
  • 空间复杂度：哈希表最多存储 min(n, modulo) 个不同的前缀和模值

相关题目