【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…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
