写点什么

每日一题:LeetCode-560. 和为 K 的子数组

作者:半亩房顶
  • 2024-01-16
    北京
  • 本文字数:900 字

    阅读完需:约 3 分钟

每日一题:LeetCode-560. 和为 K 的子数组

刷题使我快乐,满脸开心.jpg


题目

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。


子数组是数组中元素的连续非空序列。


示例 1:


输入:nums = [1,1,1], k = 2输出:2
复制代码


示例 2:


输入:nums = [1,2,3], k = 3输出:2
复制代码


提示:


  • 1 <= nums.length <= 2 * 104

  • -1000 <= nums[i] <= 1000

  • -107 <= k <= 107

思路

暴力可破,关键就在于怎么优化了。

前缀和

  • 对于这类连续数组求和的场景,前缀和是个很不错的思路。


即用一个连续累计加和的数组做辅助,以各个累计和之间的间隙差值来尝试匹配结果

哈希表

  • 而对于匹配间隙来说,我们就需要一个方式来进行搜索,这里可以考虑哈希表,搜索匹配更快。

  • 因为有负数0存在,所以很有可能会出现累加和出现重复,所以哈希表需要记录数量,而不是单单记录是否存在。

  • 不过哈希表也有一个弊端,那就是累加和需要的是有序,但对于是否存在这个结果上,哈希表是无序的,所以在代码编排上,我们就需要从前往后搜索匹配,保证结果的正确性。


至此,也就没有太多可说的了,细节在代码注释了。

代码

func subarraySum(nums []int, k int) int {    // 求前缀和数组    sums := make([]int, len(nums)+1)    for i := range nums {        sums[i+1] = sums[i] + nums[i]    }
// map缓存前缀和 sumMap := make(map[int]int, len(nums)) // 初始化 sumMap[0] = 1 res := 0 // nums[0] 没有'前缀',所以 sums[0] 无实际意义,需从 sums[1] 开始 for i := 1; i < len(sums); i++ { if _, ok := sumMap[sums[i]-k]; ok { // 如果多次进入,说明有多个起点可以累加至 i 位置满足情况 res += sumMap[sums[i]-k] } // 对累加过来的结果进行 +1,后续有相同累加结果时再 +1 // 后续再出现 sums[i]-k == 0 时,说明有两个位置可以累加至此满足情况 // 确实应该 +2,所以不用担心正确性 sumMap[sums[i]] += 1 } return res}
复制代码




欢迎关注公众号交流更多题目~


发布于: 刚刚阅读数: 3
用户头像

半亩房顶

关注

人生那么长,能写多少bug? 2018-11-16 加入

我希望,自己永远是自己。我希望,远离bug。

评论

发布
暂无评论
每日一题:LeetCode-560. 和为 K 的子数组_Go_半亩房顶_InfoQ写作社区