算法:974.和可以被K整除的子数组
题目
链接:leetcode链接

思路分析(前缀和 + 同余定理)
首先,我们要了解一下什么是同余定理
同余定理:
如果(a - b)/ p = k …… 0
则 a % p == b % p
证明我写在草稿纸上,如下图:

初此之外,我们还需要理解一个问题
在C++/java中负数取模会怎么样呢?
比如 - 2 % 5等于多少呢?
按道理来说应该是3,但是C++/java里的答案是-2
这明显是需要进行修正的
如何进行修正呢?
我们只需要( a % p + p)% p
这样,无论是正数取模还是负数取模都不会出现问题。
OK,到这里前置知识讲完了,我们就正式开始讲思路了。
需要找一个子数组的和是k的倍数
那么只需要找两个区间的前缀和对k取模的余数相同即可。
和这道题的思路非常相似
传送门:560.和为k的子数组
我们利用滚动数组去求前缀和,
记录sum % k的余数
然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可
将sum% k的余数放到hash表中(一定要是先查找在插入)
细节:
(1)什么时候插入hash表
一定要是先查找,在插入
(2)对于[0 , i]区间的和正好是K的倍数的情况如何处理
还是一样,我们先去把余数0提前先往hash表里插一个即可
具体原因可以查看和为k的子数组这篇文章
代码
//同余定理int subarraysDivByK(vector<int>& nums, int k) {int sum = 0,ret = 0;unordered_map<int,int> hash;//hash表里面放余数hash[0] = 1;//这个0依旧是存的余数for(auto& e:nums){sum += e;int check = (sum % k + k) % k; // 对余数进行修正很关键if(hash.count(check)) ret += hash[check]; hash[check]++;}return ret;}
相关文章:
算法:974.和可以被K整除的子数组
题目 链接:leetcode链接 思路分析(前缀和 同余定理) 首先,我们要了解一下什么是同余定理 同余定理: 如果(a - b)/ p k …… 0 则 a % p b % p 证明我写在草稿纸上,如下图: 初…...
QD1-P8 HTML 格式化标签(font、pre、b、strong、i、u、del、s、sub、sup)
本节学习:HTML 格式化标签。 本节视频 www.bilibili.com/video/BV1n64y1U7oj?p8 一、font 标签 用途:定义文本的字体大小、颜色和 face(字体类型)。 示例 <!DOCTYPE html> <html><head><meta cha…...
红米Turbo 3工程固件预览 修复底层 体验原生态系统 默认开启diag端口
红米Turbo 3机型代码:peridot 国外版本:POCO F6 用于以下型号的小米机型:24069RA21C, 24069PC21G, 24069PC21I。搭载1.5K OLED屏、骁龙8s处理器、5000mAh电池+90W快充、5000万像素主摄。 通过博文了解 1💝💝💝-----此机型工程固件的资源刷写注意事项 2💝💝�…...
sql的调优指南及高级sql技巧
SQL调优是优化数据库性能的重要手段,涉及编写高效的SQL查询、合理设计索引、优化数据库结构等。以下是一些SQL调优指南和高级技巧: SQL调优指南 选择合适的查询方式: **避免使用SELECT ***:仅选择所需的列,减少数据传…...
生成式专题的第一节课---GAN图像生成
一、GAN的起源与发展 1.GAN的起源 GAN (生成式对抗网络)诞生于 2014 年,由 Ian Goodfellow 提出,是用于生成数据的深度学习模型,创新点是对抗性训练,即生成器与判别器的竞争关系,为图像生成、…...
中科星图GVE(案例)——AI实现建筑用地变化前后对比情况
目录 简介 函数 gve.Services.AI.ConstructionLandChangeExtraction(image1,image2) 代码 结果 知识星球 机器学习 简介 AI可以通过分析卫星图像、航拍影像或其他地理信息数据,实现建筑用地变化前后对比。以下是一种可能的实现方法: 数据获取&am…...
Spring Boot中获取application.yml中属性的几种方式
在Spring Boot应用程序中,可以通过多种方式从application.yml文件中获取配置属性。以下是几种常见的方法: 1. 使用Value注解 你可以使用Value注解将application.yml中的属性注入到Spring管理的bean中。 application.yml app:name: MySpringBootAppve…...
YOLO11改进 | 注意力机制 | 结合静态和动态上下文信息的注意力机制
秋招面试专栏推荐 :深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 💡💡💡本专栏所有程序均经过测试,可成功执行💡💡💡 上下文Transformer(CoT&…...
Python中函数的使用方法
1 问题 在python的学习中,一个相同的程序可能会有多种不同的代码输入方式,那么函数这种方式是否方便快捷呢?今天我们来简单介绍函数的部分使用方法。 2 方法 定义函数:代码清单1Def function name (arguments):return result在上面…...
遨游智能终端赋能“危急特”场景,力推北斗技术规模化应用!
随着《北斗规模应用三年行动计划(2023-2025)》的发布,北京、湖北、重庆等多地出台北斗支持政策,北斗系统正稳步迈向“安全可控,泛在融合,开放兼容,服务全球”的发展目标。遨游通讯紧跟国家战略步…...
构建流媒体管道:利用 Docker 部署 Nginx-RTMP 从 FFmpeg RTMP 推流到 HLS 播放的完整流程
最近要实现一个类似导播台的功能,于是我先用 FFmpeg 实现一个参考对照的 Demo,我将其整理为一篇文章,方便后续大家或者和自己参考! 1、软件工具介绍 本次部署相关软件 / 工具如下: FFmpeg:全称是 Fast Fo…...
【汇编语言】寄存器(CPU工作原理)(六)—— 修改CS,IP的指令以及代码段
文章目录 前言1. 修改CS、IP的指令2. 问题分析:CPU运行的流程3. 代码段小结结语 前言 📌 汇编语言是很多相关课程(如数据结构、操作系统、微机原理)的重要基础。但仅仅从课程的角度出发就太片面了,其实学习汇编语言可以深入理解计…...
机器学习与神经网络:从技术前沿到诺贝尔奖的跨越与未来展望
近日,2024年诺贝尔物理学奖颁发给了机器学习与神经网络领域的研究者,这是历史上首次出现这样的情况。这项奖项原本只授予对自然现象和物质的物理学研究作出重大贡献的科学家,如今却将全球范围内对机器学习和神经网络的研究和开发作为了一种能…...
java 洛谷题单【数据结构1-2】二叉树
P4715 【深基16.例1】淘汰赛 解题思路 半区分配:将前半部分国家分配到左半区,后半部分国家分配到右半区,分别找到两个半区的最强国家。决赛和亚军确定:最后比较两个半区最强国家的能力值,失败者即为亚军,输…...
项目优化内容及实战
文章目录 事前思考Prometheus 普罗米修斯概述架构安装及使用 Grafana可视化数据库读写分离实战1-PrometheusGrafanaspringboot 事前思考 需要了解清楚:需要从哪些角度去分析实现?使用了缓存,就需要把缓存命中率数据进行收集;使用…...
科研绘图系列:R语言蝴蝶图(Butterfly Chart)
文章目录 介绍加载R包数据函数画图系统信息介绍 蝴蝶图(Butterfly Chart),也被称为龙卷风图(Tornado Chart)或双轴图(Dual-Axis Chart),是一种用于展示两组对比数据的图表。这种图表通过在中心轴两侧分别展示两组数据的条形图,形似蝴蝶的翅膀,因此得名。蝴蝶图的特点…...
【FPGA开发】Modelsim如何给信号分组
前面已经发布过了一篇关于 Modelsim 的入门使用教程,针对的基本是只有一个源文件加一个仿真tb文件的情况,而实际的工程应用中,往往是顶层加多个底层的源文件结构,如果不对信号进行一定的分组,就会显得杂乱不堪…...
Apache SeaTunnel 9月份社区发展记录
各位热爱 SeaTunnel 的小伙伴们,9月份社区月报来啦!这里将定期更新SeaTunnel社区每个月的重大进展,欢迎关注! 月度Merge Stars 感谢以下小伙伴上个月为 Apache SeaTunnel 做的精彩贡献(排名不分先后)&…...
系统架构设计师:数据库系统相关考题预测
作为系统架构设计师,在准备数据库系统相关的考试时,可以预期到的一些关键知识点包括但不限于以下几个方面: 数据库类型: 关系型数据库(RDBMS)与非关系型数据库(NoSQL)的区别及其适用场景。数据库管理系统(DBMS)的功能及组成部分。数据模型: 如何设计ER模型(实体-关…...
污水排放口细粒度检测数据集,污-水排放口的类型包括10类目标,10000余张图像,yolo格式目标检测,9GB数据量。
污水排放口细粒度检测数据集,污-水排放口的类型包括10类目标(1 合流下水道,2 雨水,3 工业废水,4 农业排水,5 牲畜养殖,6 水产养殖,7 地表径流,8 废水处理厂&…...
Qwen3.5-9B-AWQ-4bit部署指南:双卡RTX 4090-D镜像免配置快速上手
Qwen3.5-9B-AWQ-4bit部署指南:双卡RTX 4090-D镜像免配置快速上手 1. 模型概述 千问3.5-9B-AWQ-4bit是一个支持图像理解的多模态模型,能够结合上传图片与文字提示词,输出中文分析结果。这个量化版本特别适合处理以下任务: 图片主…...
十分钟用快马AI搭建中科院期刊分区查询工具原型
最近在帮实验室整理投稿期刊清单时,发现中科院分区查询是个高频需求。每次都要登录官网、输入验证码、反复跳转页面,特别影响效率。于是想做个简易查询工具,正好用InsCode(快马)平台试试快速原型开发,没想到十分钟就搭出了可用版本…...
Go性能剖析pprof工具使用
Go语言凭借其高效的并发模型和简洁的语法,成为众多开发者的首选。随着项目规模扩大,性能问题逐渐显现。如何快速定位性能瓶颈?Go内置的pprof工具正是解决这一问题的利器。本文将带你深入了解pprof的核心功能,助你轻松优化代码性能…...
在WinForm里玩转Halcon 3D点云:从C#代码导出到完整UI显示的保姆级避坑指南
在WinForm里玩转Halcon 3D点云:从C#代码导出到完整UI显示的保姆级避坑指南 当工业视觉项目需要处理复杂的三维场景时,Halcon的3D点云处理能力往往成为开发者的首选。但将Halcon的强大算法无缝集成到C# WinForm应用中,却可能遭遇一系列"…...
Unity URP 中 Mipmap 纹理多级渐远技术 解决远处纹理闪烁(摩尔纹)与性能优化的完整指南
什么是 Mipmap?Mipmap(多重贴图渐远技术)是一种经典的纹理渲染优化技术。它为每张纹理生成一系列预计算的缩小版本,从原始分辨率开始,逐级缩小至 11 像素。工作原理当 3D 场景中的物体远离摄像机时,其在屏幕…...
快速掌握C#语言基础知识点(16.访问修饰符)
关注我的动态 namespace _16.访问修饰符 {internal class Program {//私有内部类,被嵌套定义,能被直接外部类访问,外部类之外无法访问private class Class_Private{//公有public int a { get; set; }//私有private int b { get; set; }//受保…...
Kodi中文插件库终极指南:3分钟打造你的智能家庭影院
Kodi中文插件库终极指南:3分钟打造你的智能家庭影院 【免费下载链接】xbmc-addons-chinese Addon scripts, plugins, and skins for XBMC Media Center. Special for chinese laguage. 项目地址: https://gitcode.com/gh_mirrors/xb/xbmc-addons-chinese 还在…...
ai如何助力github项目管理:从智能生成readme到自动编排changelog
今天在准备一个AI图像识别工具的开源项目时,突然意识到GitHub仓库初始化其实可以很智能。以前手动创建目录、写README的日子太费时间了,现在用AI辅助开发,整个过程流畅得像有个技术助理在身边。下面记录下我的实践过程: 智能仓库…...
LFM2.5-1.2B-Thinking-GGUF入门必看:轻量模型在离线环境中的安全合规部署
LFM2.5-1.2B-Thinking-GGUF入门必看:轻量模型在离线环境中的安全合规部署 1. 模型概述 LFM2.5-1.2B-Thinking-GGUF是Liquid AI推出的轻量级文本生成模型,专为低资源环境设计。这个1.2B参数的模型采用GGUF格式,能够在各种边缘设备上高效运行…...
保姆级教程:用yangipcclient RN SDK 8.0快速给你的App加上实时对讲功能
保姆级实战:React Native应用集成实时对讲功能的完整指南 想象一下,你正在开发一款智能家居控制应用,用户反馈最强烈的需求是能够直接与家中的设备进行语音对讲。或者你负责的教育类App,小组讨论时缺少高效的实时语音沟通工具。传…...
