【C++前缀和】2845. 统计趣味子数组的数目|2073

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode 2845. 统计趣味子数组的数目

难度分：2073
给你一个下标从 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

前缀和

前缀和preSum[i]记录 前i个元素 nums[i] % modulo == k 的下标数量。注意：preSum[i] %= modulo 。
通过nums[i…j]枚举非空子数组，i <= j。枚举j，计算符合i的数量。
mValueCnt 记录preSum[i]的数量，i<=j。
k1 = preSum[j+1] ，k2 = (k1+modulo- k)%modulo。
已nums[j]结尾的趣味子数组的数量为：mValueCnt[k2]

代码

核心代码

class Solution {public:long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {vector<int> preSum(1);for (const auto& n : nums) {const auto tmp = (k == n % modulo) + preSum.back();preSum.emplace_back(tmp% modulo);}unordered_map<int, int> mValueCount;long long ret = 0;for (int j = 0; j < nums.size(); j++) {mValueCount[preSum[j]]++;const int k2 = (preSum[j + 1] + modulo - k) % modulo;ret += mValueCount[k2];}return ret;}};

单元测试

	vector<int> nums;int modulo,  k;TEST_METHOD(TestMethod1){nums = { 4,5 }, modulo = 1, k = 0;auto res = Solution().countInterestingSubarrays(nums, modulo, k);AssertEx(3LL, res);}TEST_METHOD(TestMethod11){nums = { 3, 2, 4 }, modulo = 2, k = 1;auto res = Solution().countInterestingSubarrays(nums, modulo, k);AssertEx(3LL, res);}TEST_METHOD(TestMethod12){nums = { 3,1,9,6 }, modulo = 3, k = 0;auto res = Solution().countInterestingSubarrays(nums, modulo, k);AssertEx(2LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。