
【LeetCode - 马化腾】第一次看到马总的代码
发布日期:2021-05-20 01:26:06
浏览次数:25
分类:精选文章
本文共 700 字,大约阅读时间需要 2 分钟。
优化后的文章:
最近在LeetCode上刷题,早上起来有些迟到,10点完成了今天的题目。习惯性地查看别人的评论,发现马总的评论和代码被及时删除了,加油吧!
今天的题目是找出数组中的和等于k的连续子数组的个数。这个题看起来简单,但如果不仔细分析可能很难高效解决。
我想到前缀和数组是一种常用的解决方法。前缀和数组的每个元素存储的是从数组开始到当前位置的累计和。比如,数组nums的前缀和数组s中,s[0]=0,s[1]=nums[0],s[2]=s[1]+nums[1],依此类推。
通过前缀和,我们可以快速计算任何子数组的和。具体来说,子数组从i到j的和等于s[j+1]-s[i]。所以,我们需要找到满足s[j+1]-s[i]=k的所有i<j的情况。
为了高效查找,我们可以用一个哈希表(字典)来记录前缀和出现的次数。当处理到j时,计算当前的前缀和s[j+1],检查是否存在s[i]=s[j+1]-k。如果存在,统计次数加上对应的i出现的次数。
比如示例nums = [1,1,1],k=2,前缀和数组为[0,1,2,3]。j=0时,s[0+1]=1,检查是否存在1-2=-1,没找到,次数加0。然后记录1的出现次数。j=2时,s[3]=3,检查3-2=1,已经有1出现,所以次数加1。此时总次数为1。j=3时,s[4]=3,检查3-2=1,依然有找到,次数总数变为2,与示例一致。
这种方法的时间复杂度是O(n),空间复杂度是O(n),适合大数组处理。考虑到元素可能为负数,k可能为负数,需要确保i<j且前缀和正确记录出现情况。
总之,这种方法高效且简洁,能够快速解决“连续子数组和等于k”的问题。
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2025年05月01日 08时58分53秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
淘宝天猫双十一养猫组队怎么踢人
2019-03-15
Java面试题整理,闭关在家37天“吃透”这份345页PDF,纯干货
2019-03-15
概念唱片Plastic Beach封面高清壁纸
2019-03-15
旅游后期效果Ography Lightroom预设
2019-03-15
2017CS231n笔记5.CNN
2019-03-15
vue项目报错集合
2019-03-15
图片链接
2019-03-15
LINUX-WIFI无线接入的一些东西
2019-03-15
word文档手写字母总会大写问题
2019-03-15
Redis中的key
2019-03-15
juc-09-控制并发流程工具类
2019-03-15
第一节 docker安装
2019-03-15
Linux系统时间与硬件时间及时间同步
2019-03-15
Spring 和 DI 依赖注入
2019-03-15
中序线索二叉树的遍历
2019-03-15
文字策略游戏 android studio(学习intent,textview,等等)
2019-03-15
laravel server error 服务器内部错误
2019-03-15
17_注册Github账号
2019-03-15
Linux驱动实现GPIO模拟I2C读写操作
2019-03-15