每日一题:LeetCode-560. 和为 K 的子数组
刷题使我快乐,满脸开心.jpg
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
复制代码
示例 2:
复制代码
提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
思路
暴力可破,关键就在于怎么优化了。
前缀和
对于这类连续数组求和的场景,前缀和是个很不错的思路。
即用一个连续累计加和的数组做辅助,以各个累计和之间的间隙差值来尝试匹配结果
哈希表
而对于
匹配间隙
来说,我们就需要一个方式来进行搜索,这里可以考虑哈希表,搜索匹配更快。因为有
负数
和0
存在,所以很有可能会出现累加和出现重复,所以哈希表需要记录数量,而不是单单记录是否存在。不过哈希表也有一个弊端,那就是累加和需要的是
有序
,但对于是否存在这个结果上,哈希表是无序的,所以在代码编排上,我们就需要从前往后搜索匹配,保证结果的正确性。
至此,也就没有太多可说的了,细节在代码注释了。
代码
复制代码
欢迎关注公众号交流更多题目~
版权声明: 本文为 InfoQ 作者【半亩房顶】的原创文章。
原文链接:【http://xie.infoq.cn/article/05cbfad80ea8fc626bebfba4b】。文章转载请联系作者。
评论