面试算法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)
文章目录 〇、导读一、实现可观测性平台的技术要点是什么?二、兼容全域信号量三、所谓全域信号量有哪些?四、统一采集和上传工具五、统一的存储后台六、自由探索和综合使用数据七、总结★推荐阅读《可观测性工程》直播预告直播主题直播时间预约直播 视频…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
