區間和問題：前綴和 + Hash 表 O(n) 查找連續子數組和為 K

題目大意

給長度 n (≤ 10000) 數組，查詢是否存在連續子數組和恰好等於 k。輸出起始、結束位置 (1-indexed)，多解取 s 最小、再 e 最小。不存在輸出 "No"。多測試案例。

核心轉化

前綴和 `sum[i] = a[1] + ... + a[i]`，`sum[0] = 0`。
子數組 [l, r] 和 = `sum[r] - sum[l-1] = k` ⇔ `sum[r] = sum[l-1] + k`。
掃描 r 從 1 到 n，對每個 r，查找是否存在 `l-1 < r` 使 `sum[l-1] = sum[r] - k`。用 Hash 表記錄每個前綴和**最早**出現的位置（或所有位置）。

算法流程

1. 計算 `sum[0..n]`。
2. 用 `unordered_map>` 記錄每個前綴和對應的所有位置索引（遞增）。
3. 遍歷 r = 1..n：
   目標值 `target = sum[r] - k`。
   在 `map[target]` 中二分查找**最大的 < r 的位置** 作為 `l-1`。
   找到則記錄候選答案 (l, r)。
4. 按題目要求選擇 s 最小、e 最小的答案。

代碼片段

#include 
#include 
#include 
#include 
using namespace std;

int main() {
    int n;
    while (~scanf("%d", &n)) {
        vector sum(n+1, 0);
        for (int i = 1; i <= n; ++i) {
            int x; scanf("%d", &x);
            sum[i] = sum[i-1] + x;
        }
        long long k; scanf("%lld", &k);
        unordered_map> pos;
        for (int i = 0; i <= n; ++i) pos[sum[i]].push_back(i);
        int bestL = -1, bestR = -1;
        for (int r = 1; r <= n; ++r) {
            long long target = sum[r] - k;
            auto it = pos.find(target);
            if (it != pos.end()) {
                const vector& vec = it->second;
                // 找最大的 idx < r
                int idx = upper_bound(vec.begin(), vec.end(), r-1) - vec.begin() - 1;
                if (idx >= 0) {
                    int l = vec[idx] + 1;
                    if (bestL == -1 || l < bestL || (l == bestL && r < bestR)) {
                        bestL = l; bestR = r;
                    }
                }
            }
        }
        if (bestL == -1) puts("No");
        else printf("%d %d\n", bestL, bestR);
    }
    return 0;
}

複雜度

• 時間：O(n log n) (建 map + n 次二分)，n=10000 極快。
• 空間：O(n)。

關鍵點

• **前綴和轉化** 將區間和問題變為「查找兩數之差」。
• **Hash 表存位置列表** 處理前綴和重複值（如數組含 0）。
• **二分查找** 找滿足 `l-1 < r` 的最大位置，保證區間非空且 e 最小。
• **選擇策略**：遍歷 r 遞增，找到的 l 自動滿足 s 最小（因 l = idx+1，idx 最大 → l 最小？不，需仔細：題目要求 s 最小，再 e 最小。遍歷 r 遞增，對每個 r 取最大 idx → l 最小。若多個 r 給出同樣 l，取最小 r 即 e 最小。邏輯正確。）

總結

區間和查詢問題，前綴和 + Hash 表是標準 O(n) 或 O(n log n) 解法。關鍵在於正確處理重複前綴和與邊界條件，並按題目要求選擇最優解。