IT 面试题库

场景题:如何求「和为 K 的连续子数组个数」(LeetCode 560)?为什么用前缀和 + 哈希表?

中级场景题算法工程师Java后端工程师前缀和哈希表子数组LeetCode560

题目

考察点:把「子数组和等于 K」转化为「pre[j]-pre[i]=K 即 pre[i]=pre[j]-K」的计数问题;用哈希表在 O(n) 内统计前缀和频次。属场景题。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 79 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:

  def subarraySum(nums, k):
      cnt = {0: 1}
      cur = ans = 0
      for x in nums:
          cur += x
          ans += cnt.get(cur - k, 0)
          cnt[cur] = cnt.get(cur, 0) + 1
      return ans
  
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题