【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…...
数字教学时代:构建高效在线帮助中心的重要性
在数字化教学日益普及的今天,教育领域正经历着前所未有的变革。随着在线课程、虚拟教室、智能学习平台等数字化工具的广泛应用,教育资源的获取方式和学习模式发生了深刻变化。然而,这种变革也带来了新的挑战,其中之一便是如何确保…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
Qt Quick Controls模块功能及架构
Qt Quick Controls是Qt Quick的一个附加模块,提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中,这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构,与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...
