Hiểu bài toán

Cho một mảng gồm n số nguyên a[1], a[2], ..., a[n]. Nhiệm vụ là đếm số lượng cặp chỉ số (l, r) sao cho 1 ≤ l ≤ r ≤ n và tổng các phần tử từ chỉ số l đến r bằng 0. Nói cách khác, tìm số lượng mảng con liên tiếp có tổng bằng 0.

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

Cách Brute Force

int count = 0;
for (int l = 1; l <= n; l++) {
    long long sum = 0;
    for (int r = l; r <= n; r++) {
        sum += a[r];
        if (sum == 0) {
            count++;
        }
    }
}
cout << count;

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

Cách tiếp cận này sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài chọn điểm bắt đầu (l) của mảng con, vòng lặp trong chọn điểm kết thúc (r) và tính tổng từng phần. Nếu tổng bằng 0 thì tăng biến đếm. Cách này đơn giản nhưng rất chậm và chỉ phù hợp với n rất nhỏ (ví dụ n ≤ 5000).

Cách Prefix Sum + Hash Map (Optimal)

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

int main() {
    ifstream fin("ZERO.INP");
    ofstream fout("ZERO.OUT");

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

    unordered_map<long long,int> cnt;
    cnt[0] = 1;  // Prefix sum = 0 exists once initially
    long long sum = 0;
    long long res = 0;
    for(int i=0;i<n;i++){
        sum += a[i];
        if(cnt.count(sum)) res += cnt[sum];
        cnt[sum]++;
    }

    fout << res << endl;
    return 0;
}

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

Phương pháp này sử dụng tổng tiền tố (prefix sum). Gọi S[i] là tổng các phần tử từ a[1] đến a[i]. Tổng của mảng con từ l đến r bằng S[r] - S[l-1]. Để tổng này bằng 0, ta cần S[r] = S[l-1]. Bằng cách duyệt qua mảng và lưu trữ tần suất xuất hiện của các tổng tiền tố vào một map (hoặc hash map), ta có thể đếm số cặp chỉ số hợp lệ. Cụ thể, tại mỗi bước i, ta kiểm tra xem tổng tiền tố hiện tại S[i] đã xuất hiện bao nhiêu lần trước đó. Mỗi lần xuất hiện trước đó tương ứng với một điểm l-1 sao cho tổng mảng con từ l đến i bằng 0. Sau đó ta cập nhật tần suất của S[i].

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

Bài học kinh nghiệm

• Bài toán quy về bài toán tìm hai chỉ số i, j sao cho tổng tiền tố tại i bằng tổng tiền tố tại j (S[i] = S[j]).
• Việc sử dụng Hash Map cho phép tra cứu tần suất các tổng tiền tố đã xuất hiện trong thời gian O(1) trung bình, giúp giải quyết bài toán trong thời gian tuyến tính O(n).

Lỗi thường gặp

• Quên khởi tạo giá trị ban đầu cho tổng tiền tố bằng 0 (cnt[0] = 1). Nếu không, các mảng con bắt đầu từ phần tử đầu tiên mà có tổng bằng 0 sẽ bị bỏ sót.
• Sử dụng long long để lưu trữ tổng tiền tố để tránh tràn số (overflow) khi các phần tử trong mảng hoặc n quá lớn.