【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”的问题。

上一篇:Finger.01 - ESP8266模块STA模式调试
下一篇:【异或的巧妙使用】求只出现一次的数字

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2025年05月01日 08时58分53秒