力扣算法笔试题复习:[子串] 和为K的子数组

560. 和为 K 的子数组

原题地址：https://leetcode.cn/problems/subarray-sum-equals-k/

题目给定一个整数数组 nums 和一个整数 k，要求统计数组中和等于 k 的连续子数组个数。

注意，这里要求的是子数组，也就是原数组中连续的一段区间，而不是可以随意挑选元素的子序列。

举个例子，nums = [1, 1, 1]，k = 2，输出为 2。因为满足条件的连续子数组有两个，分别是下标 0 到 1 的 [1, 1]，以及下标 1 到 2 的 [1, 1]。

再看一个，nums = [1, 2, 3]，k = 3，输出为 2。满足条件的连续子数组分别是 [1, 2] 和 [3]。

这道题很容易先想到滑动窗口，但这里有一个重要限制：数组中可能包含负数。负数会破坏窗口和的单调性，导致"和大了就缩小窗口、和小了就扩大窗口"这个逻辑不再可靠。因此，这题更适合用前缀和 + 哈希表来处理。

第一种：枚举所有子数组（会超时）

最容易想到的做法，是枚举所有连续子数组，并计算它们的和。如果某段子数组的和等于 k，就把答案加一。

可以固定左端点 start，然后不断向右扩展右端点 end，在扩展过程中维护当前区间和 current_sum。这样不需要每次都重新求和。

from typing import List

classSolution:
defsubarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        n = len(nums)

for start in range(n):
            current_sum = 0
for end in range(start, n):
                current_sum += nums[end]
if current_sum == k:
                    count += 1

return count

这段代码的含义很直接：外层循环固定子数组的起始位置 start，内层循环枚举子数组的结束位置 end，current_sum 表示当前子数组 nums[start:end+1] 的和。如果 current_sum == k，说明找到一个合法子数组。

比如 nums = [1, 1, 1]，k = 2：从下标 0 开始可以找到 [1, 1]，从下标 1 开始也可以找到 [1, 1]，从下标 2 开始没有满足条件的区间，最终答案为 2。

这种方法容易理解，但需要枚举所有起点和终点，时间复杂度是 O(n²)。当数组长度较大时，会超时。

时间复杂度 O(n²)，空间复杂度 O(1)。

第二种：前缀和 + 哈希表（推荐写法）

要把时间复杂度降到 O(n)，需要避免重复枚举区间。这里可以使用前缀和。

前缀和可以理解为"从数组开头累加到当前位置的和"。如果某一段连续子数组的和等于 k，本质上就是两个前缀和之间的差等于 k。

假设当前遍历到的位置前缀和为 prefix_sum，如果此前存在某个前缀和 needed_prefix = prefix_sum - k，那么从那个前缀和之后到当前位置的这段子数组，和就正好等于 k。

因此，遍历数组时只需要维护两个东西：

• 当前前缀和 prefix_sum；
• 一个哈希表 prefix_count，记录每种前缀和此前出现过多少次。

代码如下：

from typing import List
from collections import defaultdict

classSolution:
defsubarraySum(self, nums: List[int], k: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1

        prefix_sum = 0
        count = 0

for num in nums:
            prefix_sum += num

            needed_prefix = prefix_sum - k
if needed_prefix in prefix_count:
                count += prefix_count[needed_prefix]

            prefix_count[prefix_sum] += 1

return count

这里的变量含义需要讲清楚。prefix_sum 表示当前遍历位置的前缀和；prefix_count 记录某个前缀和出现过多少次；needed_prefix = prefix_sum - k 表示为了让当前这段子数组和为 k，前面需要出现过的前缀和；count 则是满足条件的子数组数量。

其中最关键的一句是 count += prefix_count[needed_prefix]。这里不是简单地加 1，而是加上 needed_prefix 这个前缀和此前出现的次数。原因是同一个前缀和可能出现多次，每一次出现都对应一个不同的起点位置，只要它们的前缀和都等于 needed_prefix，那么从这些位置之后到当前位置的子数组和都等于 k。

举个例子，nums = [1, -1, 1]，k = 1。遍历到最后一个 1 时，当前前缀和为 1，需要找的是 needed_prefix = 1 - 1 = 0。而前缀和 0 在前面出现过两次：一次是初始状态，表示从数组开头开始；一次是遍历完 [1, -1] 后。因此此时可以一次性贡献两个答案：[1, -1, 1] 和 [1]。这也解释了为什么哈希表里存的是"出现次数"，而不是只存"是否出现过"。

为什么 prefix_count[0] = 1 ？

prefix_count[0] = 1 表示在遍历数组之前，已经存在一个前缀和为 0 的"空前缀"。这个初始化是为了处理从下标 0 开始的子数组。

比如 nums = [1, 2, 3]，k = 3。当遍历到下标 1 时，当前前缀和是 3，此时 needed_prefix = 3 - 3 = 0。如果哈希表里提前记录了前缀和 0 出现过一次，就能正确识别出 [1, 2] 这段从下标 0 开始的子数组。如果没有这个初始化，那么所有从数组开头开始、和正好为 k 的子数组都会被漏掉。

为什么要先统计答案，再更新当前前缀和？

循环里的顺序也很重要：必须先用当前前缀和去查找之前出现过的 needed_prefix，再把当前 prefix_sum 加入哈希表。

原因是当前前缀和代表的是"到当前位置为止"的和，它只能作为后续子数组的左边界参考，不能提前参与当前这一轮的匹配。先查询、后更新，可以保证查到的都是当前位置之前的前缀和。

尤其在 k = 0 的情况下，这个顺序很容易写错。如果先更新当前前缀和，再查询，就可能把当前前缀和自己也算进去，导致统计出长度为 0 的非法子数组。

整个过程只需要从左到右遍历一遍数组，每个元素只处理一次。哈希表的查询和更新平均都是 O(1)，所以时间复杂度是 O(n)。哈希表最多会记录 n + 1 个不同的前缀和，因此空间复杂度是 O(n)。