Hiểu bài toán

Cho một mảng gồm n số nguyên và một số nguyên k, đếm số lượng các đoạn con liên tiếp có tổng bằng k. Các đoạn con có thể rỗng (tổng = 0) nếu k = 0.

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

Cách Brute Force (Duyệt tất cả đoạn con)

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

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

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += a[j];
            if (sum == k) cnt++;
        }
    }
    cout << cnt;
    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 để duyệt qua 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 đoạn con từ i đến j. Nếu tổng bằng k thì tăng biến đếm. Cách này chậm và chỉ phù hợp với n nhỏ (<= 10^4) do độ phức tạp O(n^2).

Cách Hash Map (Prefix Sum)

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

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

    int n;
    long long k;
    cin >> n;

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

    cin >> k;

    map<long long, int> m;
    long long sum = 0;
    long long cnt = 0;

    m[0] = 1;

    for(long long x : a) {
        sum += x;
        if(m.find(sum - k) != m.end()) {
            cnt += m[sum - k];
        }
        m[sum]++;
    }

    cout << cnt;
    return 0;
}

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

Sử dụng kỹ thuật Prefix Sum (tổng tiền tố). 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ừ chỉ số j+1 đến i là S[i] - S[j]. Ta cần tìm số cặp (i, j) sao cho S[i] - S[j] = k, hay S[j] = S[i] - k. Trong quá trình duyệt và tính S[i], ta dùng một map (bản đồ) để lưu trữ tần suất của các giá trị S[j] đã gặp. Nếu S[i] - k đã xuất hiện trong map, ta cộng số lần nó xuất hiện vào kết quả. Độ phức tạp là O(n log n) do thao tác với map.

Cách Hash Map (Optimized)

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

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

    int n;
    long long k;
    cin >> n;

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

    unordered_map<long long, int> m;
    m[0] = 1;

    long long sum = 0;
    long long ans = 0;

    for (long long x : a) {
        sum += x;
        if (m.count(sum - k)) {
            ans += m[sum - k];
        }
        m[sum]++;
    }

    cout << ans;
    return 0;
}

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

Đây là phiên bản tối ưu của phương pháp Hash Map. Thay vì dùng std::map (cây đỏ-đen, O(log n)), ta sử dụng std::unordered_map (bảng băm, trung bình O(1)). Logic tính toán giống hệt: lưu trữ tần suất các tổng tiền tố vào bảng băm và kiểm tra xem tổng tiền tố hiện tại trừ đi k có xuất hiện trước đó hay không. Trung bình độ phức tạp thời gian là O(n), tối ưu hơn O(n log n) của phương pháp trước.

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

Bài học kinh nghiệm

• Bài toán có thể chuyển đổi thành bài toán tìm hai chỉ số i, j sao cho tổng tiền tố S[i] - S[j] = k.
• Kỹ thuật Prefix Sum kết hợp với Hash Map (hoặc Hash Table) cho phép giải quyết bài toán trong thời gian tuyến tính O(n) thay vì O(n^2).
• Khởi tạo map với {0: 1} là bắt buộc để xử lý trường hợp đoạn con bắt đầu từ đầu mảng (tức S[j] = 0).

Lỗi thường gặp

• Quên khởi tạo map với giá trị 0 cho tổng tiền tố ban đầu, dẫn đến bỏ sót các đoạn con tính từ phần tử đầu tiên.
• Sử dụng biến lưu tổng có thể bị tràn số (overflow) nếu chỉ dùng int, cần dùng kiểu dữ liệu lớn hơn như long long.
• Trường hợp k = 0: Cần đếm các đoạn con có tổng bằng 0. Phương pháp Hash Map vẫn hoạt động chính xác (tìm S[i] = S[j]).