[Leetcode 560] 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中 元素的 连续 非空 序列。
比如在：nums = [1, 2, 3] 中，[1, 2] 是子数组，[1, 3] 不是子数组，因为中间跳过了 2。
 
示例 1：
示例 2：
 
滑动窗口依赖窗口和的单调变化。但这题允许负数，加入元素不一定让和变大，移除元素也不一定让和变小。因此不能保证线性扫描不重不漏。
 

解法一：暴力枚举

最直接的思路是：既然题目问有多少个子数组的和等于 k，那我们就把所有子数组都枚举出来，一个个检查它们的和是不是 k。
对于一个长度为 n 的数组，子数组由两个边界决定：左边界 left 和右边界 right。只要确定了这两个边界，就确定了一个连续子数组 nums[left:right + 1]。
所以我们可以枚举每个起点 left，然后不断向右扩展 right，在扩展过程中维护当前子数组的和 curSum。每次扩展后，如果 curSum == k，答案就加一。
这个做法的问题在于：有大量可能的连续区间，把所有连续区间完整扫一遍，逐个区间去算，没有试图跳过任何可能性，复杂度高。
复杂度分析
  • 时间复杂度是 O(n^2)。
    • 一共有 O(n^2) 个连续子数组，每个子数组通过滚动累加的方式在 O(1) 时间内得到当前和。
    • 如果每次都用 sum(nums[left:right + 1]) 重新计算区间和，那么时间复杂度甚至会退化到 O(n^3)。
  • 空间复杂度是 O(1)，只使用了常数个额外变量。

解法二：前缀和数组 + 哈希表

连续区间的和可以表示成两个前缀和的差，即 sum(nums[i:j]) = prefix[j] - prefix[i]
如果 sum(nums[i:j]) = k，那么 prefix[i] = prefix[j] - k
当我们固定右端点 j 时，当前前缀和是 prefix[j]。我们不需要重新枚举所有左端点 i 去计算区间和，只需要知道在 j 左边，有多少个 i 对应的 prefix[i] = prefix[j] - k 。
因此我们用哈希表维护“前缀和出现次数”：
遍历数组时，
  • 先更新当前前缀和 prefix[j]，
  • 再查询 prefix[j] - k 在哈希表中出现过多少次，把这个次数加入答案，
  • 最后把当前前缀和加入/更新到 哈希表。
复杂度分析
  • 时间复杂度是 O(n)
      • 我们先计算前缀和数组，再遍历前缀和数组，每一步哈希表查询和更新都是均摊 O(1)。
  • 空间复杂度是 O(n)
      • 前缀和数组需要 O(n) 空间，哈希表最多也会存 O(n) 个不同前缀和。

解法三：前缀和 + 哈希表，一次遍历 （最优解）

上一个解法已经是线性时间，但它显式地用一次遍历构造了整个前缀和数组 prefix。其实没有必要。
我们真正需要的不是所有前缀和数组本身，而是：
  1. 当前遍历到这里时的前缀和 curSum；
  1. 当前下标之前，各种前缀和分别出现过多少次。
所以可以一边遍历 nums，一边维护当前前缀和，一边用哈希表prefixCount统计历史前缀和。
每次来到一个新元素 x，
  • 我们更新 curSum ： curSum += x
  • 计算有多少个历史前缀和 prevSum，满足 curSum - prevSum == k？
      • 只需要查 prefixCount[curSum - k] ，把这个次数加入答案，
  • 然后再把当前 curSum 加入哈希表，供后面的元素使用。
这个顺序非常重要：先查，再更新当前前缀和的出现次数。 因为当前前缀和只能作为未来子数组的左边界，不能在同一轮里被自己使用。尤其当 k = 0 时，如果先更新再查询，就可能把长度为 0 的空区间错误地算进去。
复杂度分析
  • 时间复杂度是 O(n)。数组只遍历一次，每次做常数次哈希表操作。
  • 空间复杂度是 O(n)。最坏情况下，每个位置产生的前缀和都不同，哈希表会存 n + 1 个前缀和。
 
Buy Me a Coffee
上一篇
[Leetcode 473] 火柴拼正方形
下一篇
Production Agents Need Workflow Graphs

Relate Posts

Implementing Efficient Prefix Search with Tries