想要精通算法和SQL的成长之路 - 连续的子数组和
想要精通算法和SQL的成长之路 - 连续的子数组和
- 前言
- 一. 连续的子数组和
- 1.1 最原始的前缀和
- 1.2 前缀和 + 哈希表
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 连续的子数组和
原题链接

1.1 最原始的前缀和
如果这道题目,用前缀和来算,我们的思路一般是这样:
- 计算这个数组的前缀和。
- 循环遍历数组的每个元素,以每个元素作为起点,向后寻找第二个元素(索引至少是起点+2)作为终点,计算两者的区域和。再判断是否满足条件。
那么这样的代码写出来就是这样:
public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;// 计算前缀和int[] preSum = new int[n + 1];for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + nums[i];}// i 遍历到 preSum。length -2 即可,for (int i = 0; i < n - 1; i++) {// 区间长度 > 2for (int j = i + 2; j <= n; j++) {// 前缀和差即是[i,j]之间的区域和int diff = preSum[j] - preSum[i];if (diff % k == 0) {return true;}}}return false;
}
结果如下:

1.2 前缀和 + 哈希表
我们从这段代码入手:
int diff = preSum[j] - preSum[i];
if (diff % k == 0) {return true;
}
即:
- (preSum[j] - preSum[i] ) % k = 0;
- preSum[j] % k == preSum[i] % k;
那么我们只需要利用哈希表,记录每个前缀和对于k的一个取模值是多少即可,1. 存储的是它们的下标。
2. 如果遇到取模值相同的,并且两个下标差 > 2,就满足条件。
那么代码优化:
public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;// 计算前缀和int[] preSum = new int[n + 1];for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + nums[i];}HashSet<Integer> set = new HashSet<>();for (int i = 2; i <= n; i++) {set.add(preSum[i - 2] % k);if (set.contains(preSum[i] % k)) {return true;}}return false;
}
相关文章:
想要精通算法和SQL的成长之路 - 连续的子数组和
想要精通算法和SQL的成长之路 - 连续的子数组和 前言一. 连续的子数组和1.1 最原始的前缀和1.2 前缀和 哈希表 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 连续的子数组和 原题链接 1.1 最原始的前缀和 如果这道题目,用前缀和来算,我们的思路…...
【C++】头文件chrono
2023年10月16日,周一晚上 当前我只是简单的了解了一下chrono 以后可能会深入了解chrono并更新文章 目录 功能原理头文件chrono中的一些类头文件chrono中的数据类型一个简单的示例程序小实验:证明a的效率比a高 功能 这个chrono头文件是用来处理时间的…...
Python学习六
前言:相信看到这篇文章的小伙伴都或多或少有一些编程基础,懂得一些linux的基本命令了吧,本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python:一种编程语言&…...
Springboot 集成 WebSocket
WebSocket是一种在单个TCP连接上进行全双工通信的协议。WebSocket使得客户端和服务器之间的数据交换变得更加简单,允许服务端主动向客户端推送数据。在WebSocket API中,浏览器和服务器只需要完成一次握手,两者之间就直接可以创建持久性的连接…...
谨以此篇,纪念我2023年曲折的计算机保研之路
目录 阶段一:迷茫阶段二:准备个人意愿保研材料准备套磁老师5.1日 浙大线上编程测试5.8日 浙大线上面试 —— 一面5.17日 浙大线上面试——二面5.29日 实验室面试结果5.27日 南开线上面试6.20日 华师电话面试 阶段三:旅途北航CS(6.…...
VSS、VDD、VBAT、VSSA
引言 在学习设计TM32时,发现芯片除了GPIO引脚外还会引出许多引脚,以STM32F407ZGT6为例除了GPIO引脚还会有以下引脚 如VSS、VDD、VBAT、VSSA、NRST、VREF、VDDA、VCAP_1、VCAP_2、PDR_ON这些引脚。他们有何作用,电路设计中应如何连接&#x…...
【Rust基础③】方法method、泛型与特征
文章目录 6 方法 Method6.1 定义方法self、&self 和 &mut self 6.2 自动引用和解引用6.3 关联函数 7 泛型和特征7.1 泛型 Generics7.1.1 结构体中使用泛型7.1.2 枚举中使用泛型7.1.3 方法中使用泛型为具体的泛型类型实现方法 7.1.4 const 泛型 7.2 特征 Trait7.2.1 为类…...
48.排列问题求解
思路分析:通过为每一队分配一个id,join条件要求t1.num < t2.num实现相同两队只比一次 代码实现: with t as (SELECT team_name,caseteam_nameWHEN 勇士 then 1WHEN 湖人 then 2WHEN 灰熊 then 3else 4end numFROM team )SELECT t1.team_…...
18.(开发工具篇Gitlab)Git如何回退到指定版本
首先: 使用git log命令查看提交历史,找到想要回退的版本的commit id. 使用git reset命令 第一步:git reset --hard 命令是强制回到某一个版本。执行后本地工程回退到该版本。 第二步:利用git push -f命令强制推到远程 如下所示: 优点:干净利落,回滚后完全回到最初状态…...
IDEA初始配置
1. 详细设置 安装完IDEA之后的简单配置。 1.1 如何打开详细配置界面 1、显示工具栏 2、选择详细配置菜单或按钮 1.2 系统设置 1、默认启动项目配置 启动IDEA时,默认自动打开上次开发的项目?还是自己选择? 如果去掉Reopen projects on …...
WM_COPYDATA传回返回值的一个方案
方案背景 适应场景,通过WM_COPYDATA进行进程间通信时,SendMessage不能返回自定义的数据,由此想到以下思路解决这个问题 A进程使用VirtualAlloc分配一块内存,通过某种方式将此地址以及A进程ID传给另一个进程B B进程使用OpenProce…...
【日常业务开发】接口性能优化
【日常业务开发】接口性能优化 缓存本地缓存分布式缓存 数据库分库分表SQL 优化 业务程序并行化异步化池化技术预先计算事务粒度批量读写锁的粒度尽快return上下文传递空间换时间集合空间大小 缓存 本地缓存 本地缓存,最大的优点是应用和cache同一个进程内部&…...
Android 10.0 禁止弹出系统simlock的锁卡弹窗功能实现
1.前言 在10.0的系统开发中,在一款产品中,需要实现simlock锁卡功能,在系统实现锁卡功能以后,在开机的过程中,或者是在插入sim卡 后,当系统检测到是禁用的sim卡后,就会弹出simlock锁卡弹窗,要求输入puk 解锁密码,功能需求禁用这个弹窗,所以就需要看是 哪里弹的,禁用…...
VulnHub lazysysadmin
一、信息收集 1.nmap扫描开发端口 开放了:22、80、445 访问80端口,没有发现什么有价值的信息 2.扫描共享文件 enum4linux--扫描共享文件 使用: enum4linux 192.168.103.182windows访问共享文件 \\192.168.103.182\文件夹名称信息收集&…...
ppt怎么压缩到10m以内?分享ppt缩小方法
在日常工作中,我们常常需要制作和分享PowerPoint演示文稿,然而,有时候文稿中的图片、视频等元素会导致文件过大,无法在电子邮件或其他平台上顺利传输。为了将PPT文件压缩到10M以内,我们可以使用一些专门的文件压缩工具…...
智能警用装备管理系统-科技赋能警务
警用物资装备管理系统(智装备DW-S304)是依托互云计算、大数据、RFID技术、数据库技术、AI、视频分析技术对警用装备进行统一管理、分析的信息化、智能化、规范化的系统。 (1)感知智能化 装备感知是整个方案的基础,本方…...
攻防千层饼
近年来,网络安全领域正在经历一场不断升级的攻防对抗,这场攻防已经不再局限于传统的攻击与防御模式,攻击者和防守者都已经越发熟练,对于传统攻防手法了如指掌。 在这个背景下,攻击者必须不断寻求创新的途径࿰…...
组件封装使用?
组件封装是指在软件开发中,将功能代码或数据封装成一个独立的、可重用的模块或组件。这种封装可以使得代码更加模块化、可维护性和可重用性。在许多编程语言和开发框架中,都有不同的方式来实现组件封装。 以下是一些常见的组件封装方法和技巧࿱…...
2.3 初探Hadoop世界
文章目录 零、学习目标一、导入新课二、新课讲解(一)Hadoop的前世今生1、Google处理大数据三大技术2、Hadoop如何诞生3、Hadoop主要发展历程 (二)Hadoop的优势1、扩容能力强2、成本低3、高效率4、可靠性5、高容错性 (三…...
Flutter笔记:发布一个电商中文货币显示插件Money Display
Flutter笔记 电商中文货币显示插件 Money Display 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/1338…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
