问题说明（含示例）

问题描述：给定一个整数数组 nums 和一个整数 k，请统计并返回该数组中和为 k 的连续子数组的个数。其中，子数组是数组中元素的连续非空序列。

示例：

1. 输入：nums = [1,1,1]，k = 2输出：2解释：和为 2 的连续子数组有两个，分别是 [1,1]（索引 0-1）和 [1,1]（索引 1-2）。

2. 输入：nums = [1,2,3]，k = 3输出：2解释：和为 3 的连续子数组有两个，分别是 [1,2]（索引 0-1）和 [3]（索引 2）。

解题关键

本题的核心解法是 “前缀和 + 哈希表”，通过将子数组和的问题转化为前缀和的差值问题，大幅降低时间复杂度，具体逻辑如下：

1. 前缀和定义：设 sum_count[i] 为数组 nums 前 i 个元素的累加和（即 sum_count[i] = nums[0] + nums[1] + ... + nums[i-1]）。例如，sum_count[0] = 0（前 0 个元素和为 0），sum_count[1] = nums[0]，sum_count[2] = nums[0] + nums[1]。

2. 核心关系推导：对于任意连续子数组 nums[j..i-1]（索引从 j 到 i-1，长度为 i-j），其和为：sum(nums[j..i-1]) = sum_count[i] - sum_count[j]。若该子数组和为 k，则满足 sum_count[i] - sum_count[j] = k，变形可得 sum_count[j] = sum_count[i] - k。

3. 问题转化：统计 “和为 k 的子数组个数”，等价于统计 “对于每个 i，前缀和 sum_count[j] = sum_count[i] - k 出现的总次数”。即遍历过程中，每计算一个当前前缀和 sum_count[i]，查询哈希表中 sum_count[i] - k 的出现次数，累加该次数即为结果。

4. 边界处理：初始化哈希表 pre_count = {0: 1}，表示 “前缀和为 0 出现过 1 次”。这是为了处理 “当前前缀和 sum_count[i] 本身等于 k” 的情况（此时 sum_count[i] - k = 0，需统计这 1 次）。

对应代码

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 哈希表：key=前缀和，value=该前缀和出现的次数；初始{0:1}处理边界（前缀和直接等于k的情况）
        pre_count = {0: 1}
        sum_count = 0  # 记录当前的前缀和（前i个元素的累加和）
        result = 0     # 记录和为k的子数组个数
        
        # 遍历数组，逐个更新前缀和并统计结果
        for num in nums:
            sum_count += num  # 累加当前元素，得到新的前缀和
            
            # 若sum_count - k在哈希表中，说明存在对应的sum_count[j]，累加其出现次数
            if sum_count - k in pre_count:
                result += pre_count[sum_count - k]
            
            # 更新哈希表：当前前缀和的出现次数+1；若不存在则默认0+1
            pre_count[sum_count] = pre_count.get(sum_count, 0) + 1
        
        return result

对应的基础知识

实现该算法需掌握以下 Python 基础语法与操作：

1. 字典（哈希表）的核心操作

   • 初始化：pre_count = {0: 1} 创建键值对字典，用于存储前缀和与对应出现次数；
   • get() 方法：pre_count.get(sum_count, 0) 尝试获取键 sum_count 对应的值，若键不存在则返回默认值 0（避免 KeyError）；
   • 键值对更新：pre_count[sum_count] = ... 为字典添加或修改键 sum_count 对应的 value（更新前缀和出现次数）。

2. 前缀和的计算通过变量 sum_count 累加遍历到的每个 num，动态维护 “当前前缀和”（前 i 个元素的和），无需额外存储所有前缀和（节省空间）。

3. for 循环遍历for num in nums 直接迭代数组元素，逐个处理每个元素对前缀和的贡献，逻辑直观且避免索引越界。

4. 条件判断与累加if sum_count - k in pre_count 判断 “目标前缀和” 是否存在，存在则将其出现次数累加到 result，实现子数组个数的统计。

5. 变量初始化

   • sum_count = 0：初始前缀和为 0（前 0 个元素的和）；
   • result = 0：初始统计结果为 0，随遍历逐步累加。

对应的进阶知识

该问题的解决涉及算法设计与复杂度优化的进阶思想：

1. 前缀和思想的本质前缀和将 “子数组和” 的计算转化为 “两个前缀和的差值”，避免了暴力法中 “枚举所有子数组并计算和” 的冗余操作（暴力法需嵌套循环，时间复杂度 O(n²)）。

2. 哈希表的优化作用哈希表的核心价值是 O (1) 时间复杂度的查询与更新：

   • 暴力法中，判断是否存在 sum_count[j] = sum_count[i] - k 需遍历所有历史前缀和（O(n) 时间）；
   • 用哈希表存储前缀和出现次数后，查询和更新均为 O(1)，总时间复杂度降至 O(n)（仅遍历数组一次）。

3. 边界处理的必要性初始化 pre_count = {0: 1} 是算法正确性的关键：

   • 当遍历到第一个元素 num = k 时，sum_count = k，此时 sum_count - k = 0，若哈希表无 0:1，则会遗漏 “子数组 [num] 和为 k” 的情况；
   • 该初始化本质是 “默认前缀和 0 出现过 1 次”，覆盖了 “前缀和直接等于 k” 的边界场景。

4. 复杂度分析

   • 时间复杂度：O(n)，n 为数组长度，仅遍历数组一次，哈希表操作均为 O(1)；
   • 空间复杂度：O(n)，哈希表最多存储 n+1 个不同的前缀和（若所有前缀和均不重复，如数组元素全为正数时）。

5. 与暴力法的对比暴力法通过嵌套循环枚举所有子数组（外层循环定起点，内层循环定终点，计算子数组和），时间复杂度 O(n²)，在 n 较大时（如 n=10^4）会超时；而 “前缀和 + 哈希表” 解法通过空间换时间，将时间复杂度优化至 O(n)，是处理大规模数组的最优方案。