【前缀和】974. 和可被 K 整除的子数组

Halo,这里是Ppeua。平时主要更新C++,数据结构算法,Linux与ROS…感兴趣就关注我bua!
974. 和可被 K 整除的子数组
- 题目:
- 示例:
- 题解:

题目:

示例:

题解:
本题与560.和为K的子数组高度相似
同样的,本题利用了前缀和的定理.当(pre[i]-pre[j-1])mod k==0时.即为所寻找的答案.
将这个式子做简单的变换.则可以得到.pre[i] mod k ==pre[j-1] mod k时即为所寻找的答案.
同样利用hash存储每一次答案.
最后的答案即为以每一个位置为数尾的符合条件的子数组个数之和。需要注意的一个边界条件是,我们需要对哈希表初始化,记录mp[0]=1的情况,这样就考虑了前缀和本身被 k 整除的情况。
由于C++没有对负数取模的操作,所以我们需要对负数的模进行处理,具体的如下:
(sum%k)的结果可能为负数,此时进行如下处理(sum%k+k)%k,
即使是远小于K的负数,其对K同余后,其负数同余值的绝对值都要小于K,所以加上K后再对K同余就是其正数的同余值.
举个例子:
(-33%5+5)%5=2
代码:
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {for(int i=1;i<nums.size();i++){nums[i]+=nums[i-1];}unordered_map<int,int>map;map[0]=1;int res=0;for(int i=0;i<nums.size();i++){int models=((nums[i]%k+k)%k);if(map.find(models)!=map.end()){res+=map[models];}map[models]++;}return res;}
};
class Solution {
public:
int subarraysDivByK(vector& nums, int k) {
for(int i=1;i<nums.size();i++)
{
nums[i]+=nums[i-1];
}
unordered_map<int,int>map;
map[0]=1;
int res=0;
for(int i=0;i<nums.size();i++)
{
int models=((nums[i]%k+k)%k);
if(map.find(models)!=map.end())
{
res+=map[models];
}
map[models]++;
}
return res;
}
};
相关文章:
【前缀和】974. 和可被 K 整除的子数组
Halo,这里是Ppeua。平时主要更新C,数据结构算法,Linux与ROS…感兴趣就关注我bua! 974. 和可被 K 整除的子数组 题目:示例:题解: 题目: 示例: 题解: 本题与560.和为K的子数组高度相似 同样的,本题利用了前缀和的定理.当(pre[i]-…...
linux页框回收之shrink_node函数源码剖析
概述 《Linux内存回收入口_nginux的博客-CSDN博客》前文我们概略的描述了几种内存回收入口,我们知道几种回收入口最终都会调用进入shrink_node函数,本文将以Linux 5.9源码来描述shrink_node函数的源码实现。 函数调用流程图 scan_control数据结构 str…...
网络运维基础问题及解答
前言 本篇文章是对于网络运维基础技能的一些常见问题的解答,希望能够为进行期末复习或者对网络运维感兴趣的同学或专业人员提供一定的帮助。 问题及解答 1. 列举 3 种常用字符编码,简述怎样在 str 和 bytes 之间进行编码和解码。 答:常用的…...
【RabbitMQ】之保证数据不丢失方案
目录 一、数据丢失场景二、数据可靠性方案 1、生产者丢失消息解决方案2、MQ 队列丢失消息解决方案3、消费者丢失消息解决方案 一、数据丢失场景 MQ 消息数据完整的链路为:从 Producer 发送消息到 RabbitMQ 服务器中,再由 Broker 服务的 Exchange 根据…...
插入排序算法
插入排序 算法说明与代码实现: 以下是使用Go语言实现的插入排序算法示例代码: package mainimport "fmt"func insertionSort(arr []int) {n : len(arr)for i : 1; i < n; i {key : arr[i]j : i - 1for j > 0 && arr[j] > …...
Linux标准库API
目录 1.字符串函数 2.数据转换函数 3.格式化输入输出函数 4.权限控制函数 5.IO函数 6.进程控制函数 7.文件和目录函数 1.字符串函数 2.数据转换函数 3.格式化输入输出函数 #include<stdarg.h>void test(const char * format , ...){va_list ap;va_start(ap,format…...
腾讯云—自动挂载云盘
腾讯云,稍微麻烦了点。 腾讯云服务器,镜像为opencloudos 8。 ### 1、挂载云盘bash #首先通过以下命令,能够看到新的数据盘,如果不能需要通过腾讯云控制台卸载后,重新挂载,并重启服务器。 fdisk -l#为 /dev…...
为Win12做准备?微软Win11 23H2将集成AI助手:GPT4免费用
微软日前确认今年4季度推出Win11 23H2,这是Win11第二个年度更新。 Win11 23H2具体有哪些功能升级,现在还不好说,但它会集成微软的Copilot,它很容易让人想到多年前的“曲别针”助手,但这次是AI技术加持的,Co…...
Opencv Win10+Qt+Cmake 开发环境搭建
文章目录 一.Opencv安装二.Qt搭建opencv开发环境 一.Opencv安装 官网下载Opencv安装包 双击下载的软件进行解压 3. 系统环境变量添加 二.Qt搭建opencv开发环境 创建一个新的Qt项目(Non-Qt Project) 打开创建好的项目中的CMakeLists.txt,添加如下代码 # openc…...
Matlab实现光伏仿真(附上30个完整仿真源码)
光伏发电电池模型是描述光伏电池在不同条件下产生电能的数学模型。该模型可以用于预测光伏电池的输出功率,并为优化光伏电池系统设计和控制提供基础。本文将介绍如何使用Matlab实现光伏发电电池模型。 文章目录 1、光伏发电电池模型2、使用Matlab实现光伏发电电池模…...
JSON.stringify()与JSON.parse()
JSON.parse() 方法用来解析 JSON 字符串 onst json {"result":true, "count":42}; const obj JSON.parse(json); console.log(typeof(json)) //string console.log(typeof(obj)) //objJSON.stringify() 方法将一个 JavaScript 对象或值转换为 JSON 字…...
neo4j教程-安装部署
neo4j教程-安装部署 Neo4j的关键概念和特点 •Neo4j是一个开源的NoSQL图形存储数据库,可为应用程序提供支持ACID的后端。Neo4j的开发始于2003年,自2007年转变为开源图形数据库模型。程序员使用的是路由器和关系的灵活网络结构,而不是静态表…...
网络面试合集
传输层的数据结构是什么? 就是在问他的协议格式:UDP&TCP 2.1.1三次握手 通信前,要先建立连接,确保双方都是在线,具有数据收发的能力。 2.1.2四次挥手 通信结束后,会有一个断开连接的过程࿰…...
java+springboot+mysql智慧办公OA管理系统
项目介绍: 使用javaspringbootmysql开发的智慧办公OA管理系统,系统包含超级管理员,系统管理员、员工角色,功能如下: 超级管理员:管理员管理;部门管理;职位管理;员工管理…...
【教程】Tkinter实现Python软件自动更新与提醒
转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn] 文件下载:https://download.csdn.net/download/sxf1061700625/88134425 示例演示: 参考代码: import os import _thread import shutil import subprocess import sys import …...
音频深度学习变得简单:自动语音识别 (ASR),它是如何工作的
一、说明 在过去的几年里,随着Google Home,Amazon Echo,Siri,Cortana等的普及,语音助手已经无处不在。这些是自动语音识别 (ASR) 最著名的示例。此类应用程序从某种语言的语音音频剪辑开始&…...
反射简述
什么是反射反射在java中起到什么样的作用获取class对象的三种方式反射的优缺点图 什么是反射 JAVA反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意一个方法和属性&…...
Kotlin泛型的协变与逆变
以下内容摘自郭霖《第一行代码》第三版 泛型的协变 一个泛型类或者泛型接口中的方法,它的参数列表是接收数据的地方,因此可以称它为in位置,而它的返回值是输出数据的地方,因此可以称它为out位置。 先定义三个类: op…...
【后端面经】微服务构架 (1-6) | 隔离:如何确保心悦会员体验无忧?唱响隔离的鸣奏曲!
文章目录 一、前置知识1、什么是隔离?2、为什么要隔离?3、怎么进行隔离?A) 机房隔离B) 实例隔离C) 分组隔离D) 连接池隔离 与 线程池隔离E) 信号量隔离F) 第三方依赖隔离二、面试环节1、面试准备2、基本思路3、亮点方案A) 慢任务隔离B) 制作库与线上库分离三、章节总结 …...
复习之kickstart无人职守安装脚本
一、kickstart简介 kickstart是红帽发行版中的一种安装方式,它通过以配置文件的方式来记录linux系统安装的各项参数和想要安装的软件。只要配置正确,整个安装过程中无需人工交互参与,达到无人值守安装的目的。 二、kickstar文件的生成 进入/…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
