leetcode 974. 和可被 K 整除的子数组(优质解法)
代码:
class Solution {public int subarraysDivByK(int[] nums, int k) {HashMap<Integer,Integer> hashMap=new HashMap();hashMap.put(0,1);int count=0; //记录子数组的个数int last=0; //前一个下标的前缀和int now=0; //当前下标的前缀和for(int i=0;i<nums.length;i++){now=last+nums[i];int r=(now%k+k)%k;count+=hashMap.getOrDefault(r,0);hashMap.put(r,hashMap.getOrDefault(r,0)+1);last=now;}return count;}
}
题解:
涉及到子数组的问题,我们一般采用滑动窗口或者前缀和来解决,滑动窗口适合解决数组中只有正数的题,而前缀和适合解决关于子数组之和的题,本题要判断哪些子数组的和能够被 k 整除,所以适合使用前缀和来解决
在解题之前,我们要先说明一个定理:同余定理,当(a - b)% c = n (整数) ,就能够推出 a % c = b % c ,这个定理是我们解题的要点,通过下图来说明解题的过程:
sum 是前缀和数组,如上图所示,x 是以 i 为尾符合条件的子数组之和,可以推出:sum[ i ] - sum[ j ] = x ,以及 x % k = 0 ,得到 (sum[ i ] - sum[ j ])% k = 0 ;根据同余定理,推得:sum[ i ] % k = sum[ j ] % k
j 是位于 0 ~ i -1 区间中的下标,也就是说在 0 ~ i -1 区间中,找到多少个符合上述条件的前缀和,就知道以 i 下标为尾,符合条件的子数组有多少
所以我们的思路就是用一个哈希表记录在 i 下标之前所有下标的前缀和 % k 的值对应的个数,以 sum[ i ] % k 为 key,个数为 value,从 0 下标开始遍历数组,在遍历到 i 下标时,我们已经知道了 i -1 下标的前缀和,i 下标的前缀和 sum[ i ] = sum[ i -1 ] +nums[ i ] ,通过 sum[ i ] % k 得到要在哈希表中寻找的 sum[ j ] % k 的值,在哈希表中 sum[ i ] % k 对应的值有多少个,就代表以 i 下标为尾,符合条件的子数组有多少个。
以该方法遍历所有的下标,便能得到所有符合条件的子数组的个数。
要注意一个细节,因为数组中存在负数,所以 sum[ i ] 可能为负数,在 java 中,负数 % 正数得到的是负数,为了去除负数的影响,所以在取模时不能直接用 sum[ i ] % k ,而是应该用式子 ( sum[ i ] % k + k)% k
还有一个细节,当哈希表初始化的时候要直接加上 key = 0,value = 1 的数据,因为不加上的话,就无法记录 nums[ i ] % k = 0 (符合条件的子数组只有 nums[ i ] 这一个数据)这种情况了
相关文章:

leetcode 974. 和可被 K 整除的子数组(优质解法)
代码: class Solution {public int subarraysDivByK(int[] nums, int k) {HashMap<Integer,Integer> hashMapnew HashMap();hashMap.put(0,1);int count0; //记录子数组的个数int last0; //前一个下标的前缀和int now0; //当前下标的前缀和for(int i0;…...

【技术】MySQL 日期时间操作
MySQL 日期时间操作 MySQL 系统时间MySQL 时间格式化MySQL 年月日时分秒周MySQL 日期计算时分秒时差日期差日期加减 MySQL 系统时间 now():系统时间,年月日时分秒current_date:系统时间,年月日current_time:系统时间&…...
测试理论知识三:测试用例、测试策略
1.测试用例 完全的测试是不可能的,对任何程序的测试必定是不完全的,那么,最显然的测试策略就是努力使测试尽可能完全。 进行测试前,推荐先使用黑盒测试的方法设计测试用例,然后使用白盒测试方法来补充的测试用例。 2…...

【clickhouse】在CentOS中离线安装clickhouse
https://packages.clickhouse.com/rpm/stable/ 通过如下命令检查是否安装过clickhouse [root172 ~]# rpm -qa | grep clickhouse 把rpm安装包放到opt/lzh目录 按照如下命令顺序安装 [root172 /]# rpm -ivh /opt/lzh/clickhouse-common-static-22.1.2.2-2.x86_64.rpm [root…...

微信商户号申请0.2费率
我们都知道,目前市场上的支付宝或者微信商户收款,无论是线上收款还是实体店收款,一般都采用0.6%的收款费率,1万元就是60元。 其实这不低的。 大多数线下实体店商家可能使用的聚合支付码可能是0.38%,1万元是38。 虽然不…...

基于单片机设计的电子指南针(LSM303DLH模块(三轴磁场 + 三轴加速度)
一、前言 本项目是基于单片机设计的电子指南针,主要利用STC89C52作为主控芯片和LSM303DLH模块作为指南针模块。通过LCD1602液晶显示屏来展示检测到的指南针信息。 在日常生活中,指南针是一种非常实用的工具,可以帮助我们确定方向࿰…...
深度学习 该用什么标准判断差异最小
决定差异最小的标准通常依赖于您的具体问题和任务。以下是一些常见的用于评估预测性能的标准和思路: 1. **均方根误差 (RMSE):** RMSE 是预测值和真实值之间差异的平方的平均值的平方根。它对较大的误差更加敏感。 from sklearn.metrics import mean_squared_error…...

汽车制造厂设备故障预测与健康管理PHM
在现代汽车制造工业中,设备的可靠性和稳定性对于保证生产线的高效运行至关重要。为了提高生产效率、降低维修成本以及确保产品质量,汽车制造厂逐渐采用设备故障预测与健康管理(PHM)系统,以实现对设备状态的实时监测和预…...

如何通过宝塔面板搭建一个MySQL数据库服务并实现无公网ip远程访问?
文章目录 前言1.Mysql服务安装2.创建数据库3.安装cpolar3.2 创建HTTP隧道 4.远程连接5.固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 宝塔面板的简易操作性,使得运维难度降低,简化了Linux命令行进行繁琐的配置,下面简单几步,通过宝塔面板cp…...

C++ Qt开发:TabWidget实现多窗体功能
Qt 是一个跨平台C图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍TabWidget标签组件的常用方法及灵活运用。 Q…...

【轻量化篇】YOLOv8改进实战 | 更换主干网络 Backbone 之 RepGhostnet,重参数化实现硬件高效的Ghost模块
YOLOv8专栏导航:点击此处跳转 前言 轻量化网络设计是一种针对移动设备等资源受限环境的深度学习模型设计方法。下面是一些常见的轻量化网络设计方法: 网络剪枝:移除神经网络中冗余的连接和参数,以达到模型压缩和加速的目的。分组卷积:将卷积操作分解为若干个较小的卷积操…...

【STM32工具篇】使用CLion开发STM32
本文主要记录使用CLion开发STM32,并调试相关功能 使用的CLion版本:2023.3.1 CLion嵌入式配置教程:STM32CubeMX项目 |CLion 文档 (jetbrains.com) OpenOCD官网下载:Download OpenOCD for Windows (gnutoolchains.com) GNU ARM工…...

elementui中的el-table,当使用fixed属性时,table主体会遮挡住滚动条的大半部分,导致很难选中。
情况: 解决: el-table加个类,这里取为class"table" 然后是样式部分: <style scoped lang"scss"> ::v-deep.table {// 滚动条高度调整::-webkit-scrollbar {height: 15px;}// pointer-events 的基本信…...

鸿蒙端H5容器化建设——JSB通信机制建设
1. 背景 2023年鸿蒙开发者大会上,华为宣布为了应对国外技术封锁的潜在风险,2024年的HarmonyOS NEXT版本中将不再兼容Android,并推出鸿蒙系统以及其自研的开发框架,形成开发生态闭环。同时,在更高维度上华为希望将鸿蒙…...

数据管理平台Splunk Enterprise本地部署结合内网穿透实现远程访问
文章目录 前言1. 搭建Splunk Enterprise2. windows 安装 cpolar3. 创建Splunk Enterprise公网访问地址4. 远程访问Splunk Enterprise服务5. 固定远程地址 前言 Splunk Enterprise是一个强大的机器数据管理平台,可帮助客户分析和搜索数据,以及可视化数据…...

MaBatis使用`ResultMap`标签手动映射详解使用
文章目录 MaBatis使用ResultMap标签手动映射详解使用1、MyBatis只能自动维护库表”列名“与”属性名“相同时的对应关系,二者不同时无法自动ORM,如下:2、在SQL中使用 as 为查询字段添加列别名,以匹配属性名:但是如果我…...
openstack-keystone服务
文章目录 keystone服务安装和配置先决条件安装并配置组件运行以下命令来安装包。编辑文件 /etc/keystone/keystone.conf 并完成如下动作:初始化身份认证服务的数据库:初始化Fernet keys:Bootstrap the Identity service: 配置 Apache HTTP 服…...

大数据HCIE成神之路之数据预处理(3)——数值离散化
数值离散化 1.1 无监督连续变量的离散化 – 聚类划分1.1.1 实验任务1.1.1.1 实验背景1.1.1.2 实验目标1.1.1.3 实验数据解析 1.1.2 实验思路1.1.3 实验操作步骤1.1.4 结果验证 1.2 无监督连续变量的离散化 – 等宽划分1.2.1 实验任务1.2.1.1 实验背景1.2.1.2 实验目标1.2.1.3 实…...

stm32 寄存器、地址、位带操作
存储器区域功能划分 4GB 的地址空间中,ARM 已经粗线条的平均分成了 8 个块,每块 512MB,每个块也都规定了用途,具体分类见表格 6-1。每个块的大小都有 512MB,显然这是非常大的,芯片厂商在每个块的范围内设计…...

记录 | gdb使用backward-cpp来美化调试log
# 在当前工程目录下 git clone https://github.com/bombela/backward-cpp.git 编辑CMakeList.txt cmake_minimum_required(VERSION 3.15)project(exampleproj LANGUAGES CXX)add_subdirectory(backward-cpp)add_executable(main main.cpp)target_sources(main PUBLIC ${BACKW…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...