Hiểu bài toán

Cho một mảng gồm n số nguyên và một số nguyên k. Nhiệm vụ của bạn là đếm số lượng các đoạn con liên tiếp của mảng có tổng bằng k. Một đoạn con liên tiếp từ chỉ số i đến j (1 ≤ i ≤ j ≤ n) có tổng bằng k nếu tổng các phần tử từ a[i] đến a[j] bằng k.

Các cách tiếp cận

Cách Brute Force

#include <iostream>
#include <vector>
using namespace std;

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

    int count = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += a[j];
            if (sum == k) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Phương pháp này sử dụng hai vòng lặp lồng nhau để xét tất cả các đoạn con liên tiếp có thể. Vòng lặp ngoài chọn điểm bắt đầu (i), vòng lặp trong chọn điểm kết thúc (j) và tính tổng các phần tử từ i đến j. Nếu tổng bằng k thì tăng biến đếm. Cách này đơn giản nhưng không hiệu quả với n lớn (ví dụ n=100,000).

Cách Hash Map (Prefix Sum)

#include <iostream>
#include <vector>
#include <map>
using namespace std;

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

    map<long long, int> prefix_counts;
    prefix_counts[0] = 1; // Tổng tiền tố 0 có 1 cách (trước mảng)

    long long current_sum = 0;
    long long count = 0;

    for (int i = 0; i < n; i++) {
        current_sum += a[i];
        // Nếu tồn tại một tổng tiền tố trước đó là (current_sum - k)
        // thì các phần tử từ sau vị trí đó đến hiện tại có tổng bằng k
        if (prefix_counts.find(current_sum - k) != prefix_counts.end()) {
            count += prefix_counts[current_sum - k];
        }
        prefix_counts[current_sum]++;
    }

    cout << count << endl;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Sử dụng kỹ thuật tổng tiền tố (Prefix Sum) kết hợp với Hash Map. Gọi S[i] là tổng các phần tử từ a[0] đến a[i]. Tổng của đoạn con từ i đến j là S[j] - S[i-1]. Ta cần tìm S[j] - S[i-1] = k, tức là S[i-1] = S[j] - k. Trong quá trình duyệt mảng, ta lưu trữ các tổng tiền tố đã gặp vào map. Với mỗi tổng tiền tố hiện tại S[j], ta kiểm tra xem S[j] - k đã xuất hiện chưa và cộng dồn số lần xuất hiện của nó vào kết quả. Đây là cách hiệu quả nhất trong các solution đã cho.

Cách Binary Search on Prefix Sum

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n + 1);
    vector<long long> pre(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        long long target = k + pre[i-1];
        // Tìm vị trí đầu tiên có tổng tiền tố >= target
        int j = lower_bound(pre.begin() + 1, pre.begin() + n + 1, target) - pre.begin();
        // Nếu tìm thấy và giá trị đúng bằng target thì tăng biến đếm
        if (j <= n && pre[j] == target) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Phương pháp này cũng sử dụng tổng tiền tố. Nó tạo một mảng tổng tiền tố pre. Với mỗi vị trí i, nó cố gắng tìm một vị trí j > i sao cho pre[j] - pre[i] = k (tức là pre[j] = pre[i] + k). Vì mảng tổng tiền tố được sắp xếp tăng dần (nếu các số a[i] dương) hoặc không đảm bảo thứ tự (nếu a[i] âm), nhưng trong solution dùng binary search, nó giả định mảng pre có thứ tự hoặc chỉ tìm kiếm trong các phần tử hợp lệ. Tuy nhiên, cách này chỉ hoạt động đúng nếu mảng pre được sắp xếp hoặc ta dùng map như Solution 3 (Solution 3 trong bài nộp là map nhưng logic hơi khác: nó cộng dồn kết quả khi tìm thấy giá trị trước đó). Solution 1 trong bài nộp đi ngược lại: với mỗi i, tìm j sao cho pre[j] = pre[i] + k. Solution 1 thực chất là O(n log n) với binary search. Solution 3 (của dainghiajustiin) là cách biến thể của Hash Map: nó cộng dồn số lượng cặp (pre[i], pre[i]-k).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Biến đổi điều kiện tổng đoạn con bằng k thành bài toán tìm cặp tổng tiền tố có hiệu bằng k: S[j] - S[i-1] = k.
• Sử dụng Hash Map (unorderedmap hoặc map) để lưu tần suất các tổng tiền tố đã duyệt qua, giúp kiểm tra sự tồn tại của (currentsum - k) trong thời gian O(1) hoặc O(log n).
• Cần chú ý trường hợp tổng tiền tố bằng 0 khi chưa có phần tử nào (pre[0] = 0).

Lỗi thường gặp

• Sử dụng biến kiểu int cho tổng có thể gây tràn số (overflow) nếu các phần tử hoặc tổng lớn. Nên dùng long long.
• Quên khởi tạo map với giá trị 0 cho tổng tiền tố ban đầu (0), dẫn đến mất các đoạn con bắt đầu từ phần tử đầu tiên.
• Trong cách dùng Binary Search, nếu mảng không được sắp xếp tăng dần (ví dụ có số âm), lower_bound có thể không tìm đúng vị trí mong muốn trừ khi ta xử lý logic lọc hoặc dùng map.