【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 <= 105
1 <= nums[i] <= 109
1 <= modulo <= 109
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++**实现。

相关文章:
【C++前缀和】2845. 统计趣味子数组的数目|2073
本文涉及的基础知识点 C算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 LeetCode 2845. 统计趣味子数组的数目 难度分:2073 给你一个下标从 0 开始的整数数组 nums ,以及整数 modulo 和整数 k 。 请你找出并统计数组…...
C++入门基础 (超详解)
文章目录 前言1. C关键字2. C的第一个程序3. 命名空间3.1 namespace的定义3.2 命名空间的嵌套3.3 命名空间使用3.4 查找优先级总结 4. C输入和输出4.1 标准输入输出 (iostream库)4.2 文件输入输出 (fstream库)4.3 字符串流 (sstream库)4.4 C格式化输出4.5 std::endl和\n的区别 …...
docker零基础入门教程
注意 本系列文章已升级、转移至我的自建站点中,本章原文为:Docker入门 目录 注意1.前言2.docker安装3.docker基本使用4.打包docker镜像5.docker进阶 1.前言 如果你长期写C/C代码,那你应该很容易发现C/C开源项目存在的一个严重问题ÿ…...
【Java SE 题库】移除元素(暴力解法)--力扣
🔥博客主页🔥:【 坊钰_CSDN博客 】 欢迎各位点赞👍评论✍收藏⭐ 目录 1. 题目 2. 解法(快慢“指针”) 3. 源码 4. 小结 1. 题目 给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素。元素的顺…...
linux文件编程_进程
1. 进程相关概念 面试中关于进程,应该会问的的几个问题: 1.1. 什么是程序,什么是进程,有什么区别? 程序是静态的概念,比如: 磁盘中生成的a.out文件,就叫做:程序进程是…...
java NIO实现UDP通讯
NIO Udp通讯工具类 import java.io.IOException; import java.net.InetSocketAddress; import java.nio.ByteBuffer; import java.nio.channels.DatagramChannel; import java.nio.channels.SelectionKey; import java.nio.channels.Selector; import java.util.Iterator;impo…...
ffmpeg如何实现视频推流?
FFmpeg是一个强大的多媒体框架,用于处理视频和音频数据。它包括了libavcodec(用于解码和编码)、libavformat(用于格式转换)、libavutil(提供一些辅助工具和函数)、libavfilter(用于音视频过滤)等多个库。 以下这些都是FFmpeg的特性 FFmpeg支持大量的音视频编解码器&…...
【HTML5】html5开篇基础(3)
1.❤️❤️前言~🥳🎉🎉🎉 Hello, Hello~ 亲爱的朋友们👋👋,这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章,请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的…...
echarts实现3D柱状图(视觉层面)根据博主改编
https://blog.csdn.net/weixin_57798646/article/details/131067725 这是原贴 在这个基础上我需要实现 一根柱子 代码如下 <!DOCTYPE html> <html lang"en" style"height: 100%"><head><meta charset"utf8"> </hea…...
【一篇文章理解Java中多级缓存的设计与实现】
文章目录 一.什么是多级缓存?1.本地缓存2.远程缓存3.缓存层级4.加载策略 二.适合/不适合的业务场景1.适合的业务场景2.不适合的业务场景 三.Redis与Caffine的对比1. 序列化2. 进程关系 四.各本地缓存性能测试对比报告(官方)五.本地缓存Caffine如何使用1. 引入maven依…...
OpenSource - 开源WAF_SamWaf
文章目录 PreSafeLine VS SamWaf开发初衷软件介绍架构界面主要功能 使用说明下载最新版本快速启动WindowsLinuxDocker 启动访问升级指南自动升级手动升级 在线文档 代码相关代码托管介绍和编译已测试支持的平台测试效果 安全策略问题反馈许可证书贡献代码 Pre Nginx - 集成Mod…...
旅游避坑指南
1.火车站旁白的小摊贩,还有周边的小饭店百分之百是黑店,不仅难吃要死而且巨黑!!! 可以地图上搜索附近的大型商超,例如泰安市的银座商超,里面的东西不仅好吃而且价格透明,还有很多当…...
矩阵系统源码搭建的具体步骤,支持oem,源码搭建
一、前期准备 明确需求 确定矩阵系统的具体用途,例如是用于社交媒体管理、电商营销还是其他领域。梳理所需的功能模块,如多账号管理、内容发布、数据分析等。 技术选型 选择适合的编程语言,如 Python、Java、Node.js 等。确定数据库类型&…...
正则表达式调试工具实战
正则表达式调试工具实战 1、新建工程QWidget工程工程名RegexTool 如果QT不会配置,请参考我的博客,QT配置 Widget.cpp 默认内容如下 2、主界面设计 三行两列,每行采用HBoxLayout作为行布局控件,内部一个Lable控件和一个TextEdit控件,采用VBoxLayout 控件包裹三个HBoxLa…...
SQL:函数以及约束
目录 介绍 函数 字符串函数 数值函数 日期函数 流程函数 约束 总结 介绍 说到函数我们都不陌生,在C,C,java等语言中都有库函数,我们在平时也是经常使用,函数就是一段代码,我们既可以自定义实现,又可以使用库里内置的函数;从来更加简洁方便的完成业务;同样的在SQL中也有…...
在Linux中将设备驱动的地址映射到用户空间
本期主题: MMU的简单介绍,以及如何实现设备地址映射到用户空间 往期链接: Linux内核链表零长度数组的使用inline的作用嵌入式C基础——ARRAY_SIZE使用以及踩坑分析Linux下如何操作寄存器(用户空间、内核空间方法讲解)…...
电脑自带dll修复在哪里,dll丢失的6种解决方法总结
在现代科技日新月异的时代,电脑已经成为我们生活中不可或缺的一部分。然而,在使用电脑的过程中,我们常常会遇到一些常见的问题,其中之一就是dll文件丢失或损坏。当这些dll文件丢失或损坏时,可能会导致某些应用程序无法…...
k8s基于nfs创建storageClass
首先安装nfs #服务端安装 yum install -y nfs-utils rpcbind #客户端安装 yum install -y nfs-utils #启动服务 并设置开启启动 systemctl start rpcbind && systemctl enable rpcbind systemctl start nfs && systemctl enable nfs #创建共享目录 mkdir -p /…...
Chrome无法拖入加载.crx扩展文件(以IDM为例)
问题原因:新版本的Chrome浏览器已不支持加载.crx文件 解决办法:将.crx文件压缩为.zip文件,解压缩后再加载到Chrome中 以IDM的.crx文件作为示例; IDM的.crx文件位于C:\Program Files (x86)\Internet Download Manager; 将IDMGCE…...
数字教学时代:构建高效在线帮助中心的重要性
在数字化教学日益普及的今天,教育领域正经历着前所未有的变革。随着在线课程、虚拟教室、智能学习平台等数字化工具的广泛应用,教育资源的获取方式和学习模式发生了深刻变化。然而,这种变革也带来了新的挑战,其中之一便是如何确保…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
