当前位置: 首页 > news >正文

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 整除的子数组(优质解法)

代码&#xff1a; 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()&#xff1a;系统时间&#xff0c;年月日时分秒current_date&#xff1a;系统时间&#xff0c;年月日current_time&#xff1a;系统时间&…...

测试理论知识三:测试用例、测试策略

1.测试用例 完全的测试是不可能的&#xff0c;对任何程序的测试必定是不完全的&#xff0c;那么&#xff0c;最显然的测试策略就是努力使测试尽可能完全。 进行测试前&#xff0c;推荐先使用黑盒测试的方法设计测试用例&#xff0c;然后使用白盒测试方法来补充的测试用例。 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费率

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

基于单片机设计的电子指南针(LSM303DLH模块(三轴磁场 + 三轴加速度)

一、前言 本项目是基于单片机设计的电子指南针&#xff0c;主要利用STC89C52作为主控芯片和LSM303DLH模块作为指南针模块。通过LCD1602液晶显示屏来展示检测到的指南针信息。 在日常生活中&#xff0c;指南针是一种非常实用的工具&#xff0c;可以帮助我们确定方向&#xff0…...

深度学习 该用什么标准判断差异最小

决定差异最小的标准通常依赖于您的具体问题和任务。以下是一些常见的用于评估预测性能的标准和思路&#xff1a; 1. **均方根误差 (RMSE):** RMSE 是预测值和真实值之间差异的平方的平均值的平方根。它对较大的误差更加敏感。 from sklearn.metrics import mean_squared_error…...

汽车制造厂设备故障预测与健康管理PHM

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

如何通过宝塔面板搭建一个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图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍TabWidget标签组件的常用方法及灵活运用。 Q…...

【轻量化篇】YOLOv8改进实战 | 更换主干网络 Backbone 之 RepGhostnet,重参数化实现硬件高效的Ghost模块

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

【STM32工具篇】使用CLion开发STM32

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

elementui中的el-table,当使用fixed属性时,table主体会遮挡住滚动条的大半部分,导致很难选中。

情况&#xff1a; 解决&#xff1a; el-table加个类&#xff0c;这里取为class"table" 然后是样式部分&#xff1a; <style scoped lang"scss"> ::v-deep.table {// 滚动条高度调整::-webkit-scrollbar {height: 15px;}// pointer-events 的基本信…...

鸿蒙端H5容器化建设——JSB通信机制建设

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

数据管理平台Splunk Enterprise本地部署结合内网穿透实现远程访问

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

MaBatis使用`ResultMap`标签手动映射详解使用

文章目录 MaBatis使用ResultMap标签手动映射详解使用1、MyBatis只能自动维护库表”列名“与”属性名“相同时的对应关系&#xff0c;二者不同时无法自动ORM&#xff0c;如下&#xff1a;2、在SQL中使用 as 为查询字段添加列别名&#xff0c;以匹配属性名&#xff1a;但是如果我…...

openstack-keystone服务

文章目录 keystone服务安装和配置先决条件安装并配置组件运行以下命令来安装包。编辑文件 /etc/keystone/keystone.conf 并完成如下动作&#xff1a;初始化身份认证服务的数据库&#xff1a;初始化Fernet keys&#xff1a;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 的地址空间中&#xff0c;ARM 已经粗线条的平均分成了 8 个块&#xff0c;每块 512MB&#xff0c;每个块也都规定了用途&#xff0c;具体分类见表格 6-1。每个块的大小都有 512MB&#xff0c;显然这是非常大的&#xff0c;芯片厂商在每个块的范围内设计…...

记录 | 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…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...