题意概括

给定一个整数数组 a 和一个整数 k。你的任务是找到所有满足其元素之和等于 k 的连续子数组，并输出这些子数组的起始和结束下标（从 1 开始计数）。

数据范围:

• 数组长度 $n$：$1 \le n \le 10^6$
• 数组中的元素 $a_i$：$-10^9 \le a_i \le 10^9$
• 目标和 $k$：$-10^{15} \le k \le 10^{15}$

基础知识

解决这个问题的核心思想是前缀和 (Prefix Sum) 和 哈希表 (Hash Map)。

1. 前缀和: 我们定义一个前缀和 pre[i] 表示原数组从下标 0 到 i-1 的元素之和。即 $pre[i] = \sum_{j=0}^{i-1} a_j$。 那么，任意一个子数组 a[j...i-1] (闭区间) 的和就可以表示为两个前缀和的差：$\sum_{l=j}^{i-1} a_l = pre[i] - pre[j]$。

2. 哈希表: 我们的目标是找到所有满足 pre[i] - pre[j] = k 的下标对 (j, i)。 将这个等式变形，我们得到 pre[j] = pre[i] - k。 因此，当我们遍历数组计算到位置 i 的前缀和 pre[i] 时，我们只需要寻找在 i 之前，有多少个位置 j 的前缀和 pre[j] 等于 pre[i] - k。 哈希表（在 C++ 中常用 std::map 或 std::unordered_map）可以帮助我们高效地完成这个查找。我们可以用哈希表存储已经出现过的前缀和及其对应的所有下标。

   • key: 前缀和的值。
   • value: 一个存储该前缀和出现过的所有位置（下标）的列表（如 std::vector）。

   当我们遍历到 i 时，计算出当前的前缀和 sum，然后在哈希表中查找 sum - k。如果找到了，就说明以当前位置 i 为结尾，存在一个或多个满足条件的子数组。哈希表中存储的 sum - k 对应的所有下标 j，都能与当前的 i-1 构成满足条件的子数组区间 [j+1, i] (这里我们假设下标从0开始，输出时转为1开始)。 同时，我们需要将当前的前缀和 sum 和它的下标 i 存入哈希表中，以供后续的计算使用。

   特别地，为了处理从数组开头就开始的子数组（即 j=0 的情况），我们需要在哈希表中预先存入 {0: [0]}，表示和为0的前缀和在位置0（数组开始前）出现过。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 函数名不超过4个字母
void solve() {
    int n;
    ll k;
    cin >> n >> k;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    map<ll, vector<int>> mp;
    mp[0].push_back(0); // 处理从头开始的子数组, pre[0]=0

    ll sum = 0;

    for (int i = 1; i <= n; ++i) {
        sum += a[i - 1]; // 当前位置i的前缀和 pre[i]
        
        // 寻找 pre[j] = pre[i] - k
        ll tar = sum - k;
        if (mp.count(tar)) {
            // 如果找到了，则 mp[tar] 中的所有下标 j
            // 都可以和当前下标 i 构成一个解 [j+1, i]
            for (int p : mp[tar]) {
                cout << p + 1 << " " << i << endl;
            }
        }
        
        // 将当前前缀和与位置存入map
        mp[sum].push_back(i);
    }
}

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

    solve();

    return 0;
}

/*
样例 1:
输入:
5 3
1 2 0 1 2
输出:
1 2
2 3
5 5

样例 2:
输入:
8 6
3 4 -1 2 4 0 2 2
输出:
1 4
2 5
7 8
*/