XingHuiSamaの宝藏之地

给你一个整数数组 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

一开始我用前缀和加for循环做的，后面发现这样时间会超，所以这里用了哈希表，降低时间复杂度

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0;
        int count = 0;
        vector<int> v = vector<int>(nums.size() + 1, 0);
        for (int i = 1; i < v.size(); i++) {
            sum += nums[i - 1];
            v[i] = sum;
        }

        unordered_map<int, int> mp;
        mp[0] = 1;

        for (int i = 1; i < v.size(); i++) {
            int temp = v[i] - k;
            if (mp.find(temp) != mp.end()) {
                count += mp[temp];
            }
            mp[v[i]]++;
        }
        return count;
    }
};

1. 算法核心思想：前缀和移项与哨兵机制

本解法的本质是通过“前缀和”将子数组求和问题转化为两点之间的差值问题，并利用哈希表将时间复杂度从 O(N2) 降维至 O(N)。

前缀和转化：子数组 nums[i...j] 的和可以表示为前 j 个元素的总和减去前 i-1 个元素的总和。寻找和为 k 的子数组，等同于寻找满足 v[j] - v[i] = k 的两个前缀和位置。
数学移项：将公式转化为 v[i] = v[j] - k。在遍历过程中，只需在哈希表中查找目标差值 temp = v[j] - k 是否出现过，即可知道当前位置之前存在多少个符合条件的子数组起点。
哨兵设计：数组 v 的长度设定为 nums.size() + 1，将索引整体向后偏移一位。首位 v[0] 作为值为 0 的哨兵，配合哈希表中的初始值，确保从原数组首个元素开始的有效子数组能够被正确统计。

2. 宏观运行机制

算法整体分为两个独立遍历阶段：

阶段一：构建前缀和序列 通过遍历原数组 nums，持续累加当前元素，并将结果记录在偏移量为 i 的前缀和数组 v 中。循环结束后，v 中完整记录了原数组所有可能的前缀和状态。
阶段二：哈希表校验与统计 首先通过 mp[0] = 1 为哈希表注入初始基准。随后遍历前缀和数组 v（从索引 1 开始）。针对每个当前前缀和，计算其所需的历史目标值 temp。若 temp 在哈希表中存在，说明曾经出现过符合条件的前缀和，直接将其出现的频次累加至总数 count 中。统计完成后，将当前前缀和作为历史记录写入哈希表，供后续循环比对。

3. 复杂度剖析

时间复杂度：O(N)。其中 N 为数组 nums 的长度。代码包含两次独立的单层循环，哈希表的单次查找和插入均摊时间复杂度为 O(1)，整体耗时呈线性规律。
空间复杂度：O(N)。算法额外开辟了长度为 N+1 的前缀和数组 v 以及一个哈希表 mp。最坏情况下哈希表中需存储 N 个不同的前缀和记录，内存消耗与输入规模成正比。