面试算法10:和为k的子数组
题目
输入一个整数数组和一个整数k,请问数组中有多少个数字之和等于k的连续子数组?例如,输入数组[1,1,1],k的值为2,有2个连续子数组之和等于2。
分析
在从头到尾逐个扫描数组中的数字时求出前i个数字之和,并且将和保存下来。数组的前i个数字之和记为x。如果存在一个j(j<i),数组的前j个数字之和为x-k,那么数组中从第i+1个数字开始到第j个数字结束的子数组之和为k。
这个题目需要计算和为k的子数组的个数。当扫描到数组的第i个数字并求得前i个数字之和是x时,需要知道在i之前存在多少个j并且前j个数字之和等于x-k。所以,对每个i,不但要保存前i个数字之和,还要保存每个和出现的次数。分析到这里就会知道我们需要一个哈希表,哈希表的键是前i个数字之和,值为每个和出现的次数。
解
public class Test {public static void main(String[] args) {int[] nums = {1, 1, 1};int result = subarraySum(nums, 2);System.out.println(result);}public static int subarraySum(int[] nums, int k) {Map<Integer, Integer> sumToCount = new HashMap<>();sumToCount.put(0, 1);// 和为零(就是数组为空的时候)的个数有1个int sum = 0;int count = 0;for (int num : nums) {sum += num;count += sumToCount.getOrDefault(sum - k, 0);// 获取和为(sum - k)的个数sumToCount.put(sum, sumToCount.getOrDefault(sum, 0) + 1);// 设置和为sum的个数}return count;}
}
相关文章:
面试算法10:和为k的子数组
题目 输入一个整数数组和一个整数k,请问数组中有多少个数字之和等于k的连续子数组?例如,输入数组[1,1,1],k的值为2,有2个连续子数组之和等于2。 分析 在从头到尾逐个扫描数组中的数字时求出前…...
王道考研操作系统
王道考研操作系统 计算机系统概述操作系统的概念操作系统的特征操作系统的发展历程操作系统内核中断和异常系统调用操作系统结构虚拟机错题 进程与线程进程控制进程通信线程和多线程模…...
HEXO 基本使用
1 新建、编辑并预览文章 1. 新建文章 hexo new [layout] title # 或 hexo n [layout] title创建文章前要先选定模板,在hexo中也叫做布局。hexo支持三种布局(layout):post(默认)、draft、page。我们先介绍如何使用已有布局…...
Webpack Sourcemap文件泄露漏洞
Webpack Sourcemap文件泄露漏洞 前言一、Webpack和Sourcemap1.1 什么是Webpack1.2 什么是Sourcemap二、漏洞利用2.1 使用reverse-sourcemap工具2.1 直接看前端代码三、漏洞挖掘漏洞修复前言 Webpack主要是用于前端框架进行打包的工具,打包后形成.js.map文件,如果.js.map文件…...
WebGL层次模型——单节点模型
目录 多个简单模型组成的复杂模型 层次结构模型 单关节模型 JointModel程序中模型的层次结构 示例程序(JointMode.js) 代码详解 绘制层次模型(draw()) 程序效果 多个简单模型组成的复杂模型 绘制…...
【链表】反转链表 II-力扣 92 题
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…...
【考研数学】高等数学第六模块 —— 空间解析几何(1,向量基本概念与运算)
文章目录 引言一、空间解析几何的理论1.1 基本概念1.2 向量的运算 写在最后 引言 我自认空间想象能力较差,所以当初学这个很吃力。希望现在再接触,能好点。 一、空间解析几何的理论 1.1 基本概念 1.向量 —— 既有大小,又有方向的量称为向…...
巨人互动|Facebook海外户Facebook客户反馈分数
Facebook客户反馈分数是一项用于衡量用户对Facebook产品和服务满意度的指标。该指标被广泛应用于各种调研和评估活动,帮助Facebook了解用户对其平台和功能的意见和建议,并从中识别出改进的机会。 巨人互动|Facebook海外户&Facebook新闻提要的算法&am…...
Tomcat多实例部署和动静分离
一、多实例部署: 多实例:多实例就是在一台服务器上同时开启多个不同的服务端口,同时运行多个服务进程,这些服务进程通过不同的socket监听不同的服务端口来提供服务。 1.前期准备: 1.关闭防火墙:systemctl …...
关于 C/C++ 中在指针前加 const 关键字的作用说明
1. 作用说明: 在指针前加 const 的用途为:不可改变指针指向的内存的值,即将该指向指向的内存中的变量置为只读(read-only) 变量。 但是,可以给 const 的指针赋值,即将具有 const 属性的指针指向别的内存地…...
Vue.js新手指南:从零开始建立你的第一个应用
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…...
【案例】--EasyExcel导入导出文件案例
目录 一、前言二、EasyExcel解析(导入)文件2.1、EasyExcel选型2.2、如何存储excel解析的文件2.3、解析格式规则的excel文件2.4、解析未知格式规则的excel文件三、EasyExcel解析(导出)文件3.1、导出基本代码实现一、前言 最近项目中,需要对excel、csv等文件进行解析,并做相关…...
深入探索图像处理:从基础到高级应用
💂 个人网站:【工具大全】【游戏大全】【神级源码资源网】🤟 前端学习课程:👉【28个案例趣学前端】【400个JS面试题】💅 寻找学习交流、摸鱼划水的小伙伴,请点击【摸鱼学习交流群】 图像处理是计算机视觉领…...
Jetpack Compose基础组件 - Image
Image的源码参数预览 Composable fun Image(painter: Painter,contentDescription: String?,modifier: Modifier Modifier,alignment: Alignment Alignment.Center,contentScale: ContentScale ContentScale.Fit,alpha: Float DefaultAlpha,colorFilter: ColorFilter? …...
UINavigationController内的页面跳转实现 UIViewController 的 present和dismiss动画
UINavigationController内部页面跳转默认为左右切换,但是当我们想向上弹出进入界面,或者向下离开界面时,需要实现UINavigationControllerDelegate 协议自行控制页面的动画(否则直接在navVc上叠加动画会导致动画结束后的那个页面,自…...
PMP对项目管理工作有什么用?
首先,项目管理岗位基本是不限行业的,所以,只要是项目管理相关的岗位,pmp证书都是能起到效果的,不用担心局限性太大,而且,pmp证书是国际证书,无论国企还是外企,都是认可这…...
Python 将‘20230919182550‘ 转换为 ‘%Y年%m月%d日 %H:%M‘
为了将给定的时间字符串 cur_time 转换为指定的格式,可以使用 Python 的 datetime 模块。以下是完成此操作的步骤: 使用 strptime 方法将 cur_time 转换为一个 datetime 对象。使用 strftime 方法将这个 datetime 对象转换为所需的格式。 这是具体的代…...
vue2.0检测无用的代码并删除
(1)、使用 useless-files-webpack-plugin 来查找无用文件 npm i useless-files-webpack-plugin -S (2)、vue.config.js中配置 const UselessFile require(useless-files-webpack-plugin)chainWebpack: config > {config.plu…...
小米华为,化干戈为玉帛!
近日来,手机圈又掀起了各大厂家推出新品的高潮。首先是华为Mate60的推出,其自研的麒麟9000S芯片瞬间点燃了国内手机市场,得到了国内甚至国外业界人士的认可和好评。 而近日网上盛传的小米创始人雷军的“愿意加入华为技术生态圈”的邀请&…...
【文末赠书】SRE求职必会 —— 可观测性平台可观测性工程(Observability Engineering)
文章目录 〇、导读一、实现可观测性平台的技术要点是什么?二、兼容全域信号量三、所谓全域信号量有哪些?四、统一采集和上传工具五、统一的存储后台六、自由探索和综合使用数据七、总结★推荐阅读《可观测性工程》直播预告直播主题直播时间预约直播 视频…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
