你好！我是你的OI竞赛教练。这道题（LeetCode 560. Subarray Sum Equals K）是非常经典的前缀和与哈希表结合的题目。在信息学奥赛中，这类“区间计数”问题非常常见。

---

一、 题目描述 (OI 风格)

题目名称： 序列区间计数 (Count Subarray Sum)

题目描述： 给定一个包含 $N$ 个整数的序列 $A = [A_0, A_1, \dots, A_{N-1}]$ 和一个整数 $K$。 请你计算该序列中有多少个连续子序列（Subarray），满足其元素之和恰好等于 $K$。

输入格式： 第一行包含两个整数 $N$ 和 $K$。 第二行包含 $N$ 个整数，表示序列 $A$ 的元素，整数之间用空格分隔。

输出格式： 输出一个整数，表示满足条件的连续子序列的总个数。

数据范围： $1 \le N \le 20,000$ $-1000 \le A_i \le 1000$ $-10^7 \le K \le 10^7$ 保证答案在 32 位有符号整数范围内。

样例输入：

3 2
1 1 1

样例输出：

2

(解释：[1,1] 和 [1,1] 是两个不同的子数组，尽管元素相同，但位置不同)

---

二、 预备知识点总结

在解决这道题之前，你需要掌握以下“工具”：

1. 前缀和 (Prefix Sum)：
   • 定义：$S[i] = A[0] + A[1] + \dots + A[i]$。
   • 核心性质：任意子数组 $A[i \dots j]$ 的和可以表示为 $S[j] - S[i-1]$。这是将 $O(N)$ 的区间求和优化为 $O(1)$ 的关键。
2. 哈希表 (Hash Map)：
   • 在 C++ 中是 std::unordered_map (C++11) 或 std::map（保留插入顺序，底层为红黑树）。
   • 用途：用于快速查找某个数值出现的次数（Key为数值，Value为频次）。
3. 同余/等式变换思维：
   • 将求和问题转化为“两数之差”问题（类似 Two Sum）。

---

三、 启发式教学与草稿纸推演

现在，拿出一张草稿纸，我们把这道题像剥洋葱一样剥开。

1. 朴素思路：暴力枚举 (Brute Force)

教练提问： “如果我不要求时间限制，你要找所有和为 $K$ 的子数组，你会怎么做？”

学生草稿： 画一个数组：[1, 2, 3]， $K=3$。 我会试：

• [1] (sum=1, no)
• [1, 2] (sum=3, yes!)
• [1, 2, 3] (sum=6, no)
• [2] (sum=2, no)
• [2, 3] (sum=5, no)
• [3] (sum=3, yes!)

代码逻辑：

// 伪代码
ans = 0
for i = 0 to N-1:       // 枚举起点
    for j = i to N-1:   // 枚举终点
        sum = 0
        for k = i to j: sum += A[k] // 求和
        if sum == K: ans++

分析： 这是 $O(N^3)$。太慢了。如果利用前缀和优化求和部分，可以降到 $O(N^2)$。 但是在 $N=20,000$ 的数据下，$N^2 = 4 \times 10^8$，对于大多数 OJ (1秒限时) 来说，这个复杂度非常危险，大概率 TLE (Time Limit Exceeded)。我们需要 $O(N)$ 或 $O(N \log N)$ 的解法。

---

2. 进阶思路：逆向思维与方程变换

教练引导： “我们利用前缀和数组 $S$。如果我想知道以位置 $j$ 结尾的某个子数组和是否为 $K$，我在找什么？”

学生思考： 子数组 $A[i \dots j]$ 的和等于 $K$。 公式是：$S[j] - S[i-1] = K$。

教练关键点拨： “很好。在遍历数组时，当我们来到位置 $j$，$S[j]$ 是已知的，$K$ 是已知的。我们需要找的是有多少个 $i$ 满足条件。 请把上面的方程变换一下，把未知数 $S[i-1]$ 放到一边。”

学生草稿推演：

$$S[j] - S[i-1] = K$$ $$\downarrow$$ $$S[i-1] = S[j] - K$$

图解过程： 假设数组 $A = [1, -1, 1, 1, 1]$， $K=2$。 我们正在遍历，现在走到了 index 3 (也就是第4个元素)。

Index ($j$)	Val ($A[j]$)	PrefixSum ($S[j]$)	目标：我们需要之前出现过几次 $S[j]-K$ ?
0	1		$1 - 2 = -1$ (找 -1 出现过几次)
1	-1	0	$0 - 2 = -2$ (找 -2 出现过几次)
2	1		$1 - 2 = -1$ (找 -1 出现过几次)
3	1	2	$2 - 2 = 0$ (找 0 出现过几次)

教练总结： 这就变成了：“在我当前位置之前，有多少个前缀和的值等于 $(S[j] - K)$ ？” 这不就是一个查找统计问题吗？我们要快速查“某个值出现过几次”，应该用什么数据结构？

学生回答： 哈希表 (Map)！

---

3. 细节完善与陷阱回避

教练： “很好。我们用一个 Map cnt 记录前缀和出现的次数。cnt[x] 表示前缀和 x 出现的次数。 但是，这里有一个巨大的坑。 如果 $A=[2]$，$K=2$。 $S[0] = 2$。 公式：找 $S[j] - K = 2 - 2 = 0$。 可是 Map 此时是空的（或者只存了当前的 2），我们怎么表示‘从头开始’的情况？”

优化建议： 我们需要在遍历之前，在 Map 中预先放入 {0: 1}。 这代表：前缀和为 0 的情况出现过 1 次（即虚拟的下标 -1 处前缀和为 0）。 这样如果 $S[j]$ 本身就等于 $K$，那么 $S[j] - K = 0$，我们就能查到这 1 次，答案正确加 1。

---

4. 复杂度分析

• 时间复杂度： 我们只需要遍历一次数组。在循环中，Map 的查找和插入操作平均是 $O(1)$ 的（使用 unordered_map）。所以总时间复杂度是 $O(N)$。
  • 注：如果使用 std::map (红黑树)，复杂度是 $O(N \log N)$，也可以通过。
• 空间复杂度： 我们需要一个 Map 来存储前缀和。最坏情况下，所有前缀和都不同，需要 $O(N)$ 的空间。

---

四、 读题理解关键词总结

做这类 OI 题时，看到以下关键词要迅速反应：

1. “连续子数组” (Continuous Subarray) $\rightarrow$ 想到 前缀和 或 滑动窗口。
2. “有负数” ($-1000 \le A_i$) $\rightarrow$ 滑动窗口失效！
   • 解释： 滑动窗口通常要求数据具有单调性（加一个数变大，减一个数变小）。有负数时，加一个数可能变小，因此不能简单地收缩左边界。这强力指向 前缀和 + 哈希表。
3. “和为 K” (Sum equals K) $\rightarrow$ 这是一个精确值查找，结合前缀和公式 $S[j] - S[i] = K$。
4. “求个数” (Total number) $\rightarrow$ 需要统计，而不是求最大长度（如果是求最长长度，Map 记的是下标；如果是求个数，Map 记的是频次）。

---

五、 OI 风格参考代码 (C++14)

/**
 * Solution for "Subarray Sum Equals K" in OI Style
 * Time Complexity: O(N)
 * Space Complexity: O(N)
 */

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义长整型，防止累加溢出（虽然题目说int够用，但OI习惯防爆）
typedef long long ll;

void solve() {
    int n;
    int k;
    
    // 1. 输入处理
    if (!(cin >> n >> k)) return;
    
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    // 2. 核心算法：前缀和 + 哈希表
    // key: 前缀和的值, value: 该前缀和出现的次数
    unordered_map<int, int> prefix_counts;
    
    // 初始化：前缀和为0出现1次（处理从头开始的子数组）
    prefix_counts[0] = 1;
    
    int current_sum = 0;
    int ans = 0;
    
    for (int i = 0; i < n; ++i) {
        current_sum += nums[i]; // 更新当前前缀和 S[j]
        
        // 目标：寻找之前的某个 S[prev] == current_sum - k
        int target = current_sum - k;
        
        // 如果 map 中存在这个 target，说明之前有若干个位置的前缀和满足条件
        if (prefix_counts.count(target)) {
            ans += prefix_counts[target];
        }
        
        // 将当前的前缀和记录到 map 中，供后面查询
        prefix_counts[current_sum]++;
    }
    
    // 3. 输出结果
    cout << ans << endl;
}

int main() {
    // 开启IO加速，OI常备
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

六、 课后思考 (Follow-up)

1. 如果题目要求输出这些子数组的起始和结束下标，代码该怎么改？（提示：Map 的 Value 需要存一个 vector<int> 来记录所有下标）。
2. 如果 $A_i$ 全部为正数，除了前缀和+哈希，还有什么方法？（提示：双指针/滑动窗口）。
3. 如果 $K$ 是 $K$ 的倍数怎么办？（提示：同余定理，$(S[j] - S[i]) \% K == 0 \implies S[j] \% K == S[i] \% K$）。