[LeetCode] 每日一题 2845. 统计趣味子数组的数目（前缀和）

题目描述

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

请你找出并统计数组中 趣味子数组 的数目。

如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：

• 在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。

以整数形式表示并返回趣味子数组的数目。

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

题目链接

https://leetcode.cn/problems/count-of-interesting-subarrays

示例输入

示例 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^5

• 1 <= nums[i] <= 10^9

• 1 <= modulo <= 10^9

• 0 <= k < modulo

解题思路

这题第一眼看上去不太像常规题型，但仔细一分析就能发现它的本质其实是个 前缀和 + 哈希计数 的问题。

我们要找的是满足某个条件的子数组数量。这个条件是：某个区间内，满足 nums[i] % modulo == k 的元素个数，记为 cnt，它本身也要满足 cnt % modulo == k。

这个“子数组统计 + 满足模运算”的组合，最直接的思路就是对满足条件的位置预处理成一个前缀和数组，也就是：

• 如果 nums[i] % modulo == k，就记为 1；

• 否则记为 0；

• 这样前缀和就变成了“某个前缀下满足条件的个数”。

接下来就是考虑某一段子数组的“左端点”有哪些满足条件。我们可以构造一个“哈希表”来存储之前所有 sum % modulo 出现的次数：

• 我们希望当前前缀和 sum，找出之前的某个 preSum，使得 (sum - preSum) % modulo == k

• 等价于 preSum % modulo == (sum - k + modulo) % modulo

• 所以只要我们维护一个 cnt[preSum % modulo] 的数组即可，在每一步更新答案。

这题思路一旦想明白，其实代码实现还是挺清爽的，而且不需要复杂的数据结构。

代码实现

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0;
        int n = nums.size();
        int[] sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (nums.get(i) % modulo == k) {
                sums[i + 1] = sums[i] + 1;
            } else {
                sums[i + 1] = sums[i];
            }
        }
        int[] cnt = new int[Math.min(modulo, n + 1)];
        for (int sum : sums) {
            if (sum >= k) {
                ans += cnt[(sum - k) % modulo];
            }
            cnt[sum % modulo]++;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)

  • 遍历一次原数组构造前缀和，再遍历一次前缀和统计答案，总体线性

• 空间复杂度：O(n)

  • 用到了前缀和数组和模拟哈希的数组，空间上是线性或者与 modulo 有关，视实际数据而定

总结

今天这题不再是经典滑窗，而是用 前缀和 + 模运算 + 哈希统计 来解决更灵活的“子数组计数”问题，非常适合练习这类前缀和差值对应关系的思考方式。

总的来说，题目形式虽然新颖，但核心技巧依旧是我们熟悉的工具链：前缀和、哈希计数与模运算的结合技巧，在刷题过程中多遇几次就会慢慢变得自然。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。