算法: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;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/447964.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Ubuntu QT 交叉编译环境搭建

文章目录 下载安装qtCreatornot a valid identifier 的错误 安装g下载并安装交叉编译器下载交叉编译器安装交叉编译器 下载编译 ARM 的Qt平台源码配置arm的QT平台 下载安装qtCreator 去QT下载官网下载对应需要的QT软件。 这里下载5.12.96版本的 改变安装包权限&#xff0c;…

红海云首届粤港澳大湾区人力资源服务创新创业大赛斩获殊荣

10月11日&#xff0c;由广东省人力资源和社会保障厅、广州市人民政府主办&#xff0c;广州市人力资源和社会保障局承办的“首届粤港澳大湾区人力资源服务创新创业大赛”决赛落下帷幕&#xff0c;红海云凭借领先的HR数字化产品创新实践斩获大赛三等奖。 本次大赛以“激活人力创…

21c RAC CLSRSC-143 CLSRSC-150 crsgpnp.pm line 2063

CLSRSC-143:Failed to create a peer profile for Oracle Cluster gpnp using ‘gpnptool’(error code 1) 21c RAC GI安装时&#xff0c;在跑root.sh时报错如下&#xff1a; 查看了下crsgpnp.pm line 2063为如下原代码 第一感觉是主机名太长了&#xff0c;将主机名缩减后…

基础IO -- 理解文件(1)

目录 一&#xff1a;回顾文件 二&#xff1a;加深对文件的理解 1.概念 2.以w写方式打开 3.以a追加方式打开 4.重定向 一&#xff1a;回顾文件 以前学习过在C语言中的文件操作&#xff0c; 但那根本是不足以理解文件的&#xff0c;即站在语言角度是不可能理解文件的 我们要…

3. 单例模式唯一性问题—构造函数

1. 构造函数带来的唯一性问题指什么&#xff1f; 对于不继承MonoBehaviour的单例模式基类 我们要避免在外部 new 单例模式类对象 例如 &#xff08;完整单例模式定义在上一节&#xff09; public class Main : MonoBehaviour {void Start(){// 破坏单例模式的唯一性&#xf…

电能表预付费系统-标准传输规范(STS)(6)

6. POSToTokenCarrierInterface 应用层协议 6.1 APDU: ApplicationProtocolDataUnit 应用协议数据单元 6.1 .1 Data elements in the APDU The APDU is the data interface between the POSApplicationProcess and the application layer protocol and comprises the data e…

新装ubuntu22.04必做两件事,不然可能没法用

一、换服务源 在全部里面找到软件和安装&#xff1b;打开后 在更多里面匹配一下最适合自己的软件源&#xff1b;这个过程比较漫长&#xff1b;要耐心等待 二、换软件安装中心 先执行&#xff1a; sudo apt upgrade 后执行&#xff1a; sudo apt install plasma-discover…

Rust默认使用UTF-8编码来解析源代码文件。如果在代码中包含无法用UTF-8编码表示的字符,编译器会报错!

文章目录 Rust默认编码示例在ANSI编码下中文显示正常的代码在UTF-8编码下将显示不正常在编译时&#xff0c;Rust使用UTF-8编码来解析代码&#xff0c;发现无法用UTF-8编码表示的字符&#xff0c;于是编译器报错 Rust默认编码 Rust 语言默认使用 UTF-8 编码来解析源代码文件。如…

免费Excel工作表同类数据合并工具

下载地址&#xff1a;https://pan.quark.cn/s/81b1aeb45e4c 在 Excel 表格里&#xff0c;当我们试图手动将多行同类数据合并为一行时&#xff0c;会遭遇诸多棘手的困难以及繁杂的操作流程。在确定哪些数据属于可合并的同类数据时&#xff0c;单纯依靠人工进行对比&#xff0c;极…

10.12学习日志

一.期望与方差 接上篇 2.方差 方差是统计学中一个重要的概念&#xff0c;用于衡量随机变量或一组数据的离散程度。它反映了数据点与其平均值之间的偏离程度。方差越大&#xff0c;数据点越分散&#xff1b;方差越小&#xff0c;数据点越集中。 对于一个随机变量 X&#xff…

JavaSE——集合7:Set接口实现类—TreeSet

目录 一、TreeSet基本介绍 二、TreeSet核心方法 三、TreeSet排序方法 四、TreeSet源码解析 1.无参构造时&#xff0c;底层是创建TreeMap对象 2.有参构造时&#xff0c;底层也创建TreeMap对象 3.执行add方法 4.执行put方法 一、TreeSet基本介绍 TreeSet是 Java 集合框架…

【报错解决】安装scikit-rebate包报错

scikit-rebate ReBATE是一套基于Relief的机器学习特征选择算法 报错信息 解决方案 conda install numpy scipy scikit-learnpip install skrebate依次运行以上两步&#xff0c;即可成功安装&#xff01;

QT的核心机制 对话框资源

案例 1、键盘按下w&#xff0c;s&#xff0c;a&#xff0c;d键分别为标签向上&#xff0c;下&#xff0c;左&#xff0c;右移动 鼠标按下获取本地坐标&#xff0c;全局坐标 鼠标双击获取本地坐标&#xff0c;全局坐标 鼠标移动获取本地坐标&#xff0c;全局坐标 让鼠标跟踪…

leetcode128最长连续序列 golang版

题目描述 题目&#xff1a;给定一个未排序的整数数组 nums 找出数字连续的最长序列&#xff0c;不要求序列 元素在原数组中连续 的长度 请你设计并实现时间复杂度为On的算法解决此问题 示例 1&#xff1a; 输入&#xff1a;nums [100,4,200,1,3,2] 输出&#xff1a;4 解释&…

前端入门学习之css盒子原则

文章目录 前端入门学习之css盒子原则引入块级元素&#xff1a;块级元素的特点占据整行设置高度和宽度包含其他元素 盒子原则&#xff1a;margin&#xff1a;例子&#xff1a; boder&#xff1a;padding&#xff1a; 前端入门学习之css盒子原则 引入块级元素&#xff1a; 当一…

Spring Boot知识管理系统:创新与实践

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常适…

MySQL-约束Constraint详解

文章目录 约束简介非空约束检查约束唯一约束列级约束与表级约束给约束起名字 主键约束主键概念以及注意事项 外键约束外键概念以及注意事项外键使用场景约束的删除与添加级联相关操作级联删除(on delete cascade)级联更新(on update cascade)级联置空(on delete set null) 约束…

从SQL Server过渡到PostgreSQL:理解模式的差异

前言 随着越来越多的企业转向开源技术&#xff0c;商业数据库管理员和开发者也逐渐面临向PostgreSQL迁移的需求。 虽然SQL Server和PostgreSQL共享许多数据库管理系统&#xff08;RDBMS&#xff09;的基本概念&#xff0c;但它们在处理某些结构上的差异可能会让人感到困惑&…

首届公安影视文化融创发展活动暨龙虎山警察文化交流季圆满收官!

为推动形成公安题材文学创作的全链条发展机制&#xff0c;搭建文化交流的平台&#xff0c;由公安部新闻传媒中心联合江西省鹰潭市人民政府举办的“首届公安影视文化融创发展活动暨龙虎山警察文化交流季”&#xff0c;于10月12日在江西省鹰潭市龙虎山举行专题总结仪式&#xff0…

如何通过构建对应的api服务器使Vue连接到数据库

一、安装数据库驱动 在后端安装 MySQL 数据库驱动&#xff0c;比如在 Node.js 环境中可以使用 mysql2 包来连接 MySQL 数据库。在项目目录下运行以下命令安装&#xff1a; npm install mysql2或者使用 yarn&#xff1a; yarn add mysql2二、创建数据库连接模块 创建一个专门…