Lời giải: Treasure Subarray (Kho Báu Đoạn Con)

Phân tích bài toán

Tìm số đoạn con liên tiếp có tổng đúng bằng \(K\). Gọi \(pref[i] = \sum_{j=1}^i a_j\) là tổng tiền tố đến phần tử thứ \(i\). Tổng đoạn con từ \(l\) đến \(r\) là: \[\text{sum}(l, r) = pref[r] - pref[l-1] = K \iff pref[l-1] = pref[r] - K\]

Thuật toán

Duyệt qua từng phần tử, duy trì tổng tiền tố current_sum và lưu trữ số lần xuất hiện của các tổng tiền tố trong std::map<long long, int>. Tại mỗi bước:

1. Cộng số lượng tiền tố bằng current_sum - K vào kết quả.
2. Tăng số đếm của current_sum trong map.

Độ phức tạp thuật toán

• Thời gian: \(O(N \log N)\) hoặc \(O(N)\) với bảng băm.
• Không gian bộ nhớ: \(O(N)\).

Mã nguồn C++ tham khảo

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    map<long long, int> pref_count;
    pref_count[0] = 1;

    long long current_sum = 0;
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        current_sum += val;
        if (pref_count.find(current_sum - k) != pref_count.end()) {
            ans += pref_count[current_sum - k];
        }
        pref_count[current_sum]++;
    }

    cout << ans << "\n";
    return 0;
}