题意概括

给定一个由整数组成的数组 nums 和一个整数 k，你的任务是计算并返回这个数组中和为 k 的连续子数组的总个数。数组中的元素可以是正数、负数或零。

数据范围:

• 数组长度 n 和目标值 k 会在输入中给出。对于典型的竞赛题目，n 的范围可能在 $1$ 到 $10^5$ 之间，k 和数组元素的值在 int 范围内。

基础知识

暴力解法是枚举所有可能的连续子数组，然后计算它们的和，时间复杂度为 $O(N^2)$，在 n 较大时无法通过。解决这个问题的最优方法是巧妙地结合 前缀和 (Prefix Sum) 与 哈希表 (Hash Map)。

核心思想：前缀和转换

1. 前缀和定义: 我们定义前缀和 pre[i] 为数组从下标 0 到 i-1 的元素之和。pre[0] 为 0。
2. 子数组和: 有了前缀和，任意一个连续子数组 nums[i..j] 的和就可以通过 pre[j+1] - pre[i] 快速计算得出。
3. 问题转换: 我们要寻找的是满足 sum(nums[i..j]) = k 的 (i, j) 对的数量。利用前缀和，这个问题就等价于寻找满足下面等式的 (i, j) 对的数量：$$\text{pre}[j+1] - \text{pre}[i] = k$$ 对这个等式进行移项，我们得到一个更具启发性的形式：$$\text{pre}[i] = \text{pre}[j+1] - k$$

算法流程：哈希表优化查找

上述转换后的等式告诉我们：当我们在遍历数组，计算到下标 j 的前缀和 pre[j+1] 时，我们所需要的，是在它之前（即 i <= j）有多少个位置 i，其前缀和 pre[i] 恰好等于 pre[j+1] - k。

如果每次都回头去查找，效率依然低下。这时，哈希表就派上了用场。我们可以用一个哈希表来记录在遍历过程中，每个前缀和值出现了多少次。

1. 初始化一个哈希表 mp 用于存储 {前缀和 -> 出现次数} 的映射，一个计数器 ans = 0，以及一个当前的前缀和 cur = 0。
2. 关键初始化: 在哈希表中预先存入 mp[0] = 1。这一步至关重要，它代表一个数值为 0 的“空”前缀和已经出现过一次。这可以正确处理那些从数组第一个元素开始就满足条件的子数组。
3. 遍历数组中的每一个元素 x： a. 更新当前的前缀和：cur += x。 b. 查找哈希表中是否存在键为 cur - k 的项。如果存在，说明在当前位置之前，存在若干个子数组的起点，使得这些子数组的和为 k。将 mp[cur - k] 的值累加到 ans。 c. 将当前的前缀和 cur 的出现次数加一，即 mp[cur]++。
4. 遍历结束后，ans 就是最终的答案。

复杂度分析:

• 时间复杂度: 我们只需要对数组进行一次遍历，每次循环中的哈希表操作（查找和插入）的平均时间复杂度为 $O(1)$，因此总时间复杂度为 $O(N)$。
• 空间复杂度: 在最坏的情况下，所有的前缀和都不同，哈希表需要存储 N 个键值对，所以空间复杂度为 $O(N)$。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    int n;
    ll k;
    cin >> n >> k;

    // mp: 存储 {前缀和 -> 出现次数} 的映射
    unordered_map<ll, int> mp;
    
    // 关键初始化：和为0的前缀和出现1次（空数组）
    mp[0] = 1;

    ll ans = 0;
    ll cur = 0; // 当前的前缀和

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cur += x;

        // 查找是否存在 pre[i] = cur - k
        // 如果 mp.count(cur - k) 存在，说明找到了
        if (mp.count(cur - k)) {
            ans += mp[cur - k];
        }

        // 将当前前缀和计入 map
        mp[cur]++;
    }

    cout << ans << endl;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
3 2
1 1 1

样例输出 1:
2

样例输入 2:
3 3
1 2 3

样例输出 2:
2
*/