Ý tưởng giải quyết:

Để giải bài toán này với thời gian tối ưu (~O(N)~):

1. Sử dụng tiền tố (prefix sum):
   • Tính tổng tiền tố của dãy ~A~: ~prefix[i] = A_1 + A_2 + \dots + A_i~.
   • Một dãy con có tổng bằng ~0~ khi ~prefix[j] - prefix[i-1] = 0~, hay ~prefix[j] = prefix[i-1]~.
   • Để kiểm tra điều này, sử dụng hash map để lưu tần suất xuất hiện của các giá trị ~prefix[j]~.

1. Thuật toán cụ thể:

   • Khởi tạo ~prefix_sum = 0~ và một hash map ~count~ để lưu tần suất các tổng tiền tố, ban đầu đặt ~count[0] = 1~ (tổng bằng ~0~ xuất hiện một lần).
   • Duyệt qua các phần tử của ~A~, cập nhật ~prefix_sum~ và kiểm tra:
     • Nếu ~prefix_sum~ đã xuất hiện trong ~count~, cộng tần suất vào tổng số dãy con.
     • Cập nhật tần suất của ~prefix_sum~ trong ~count~.

2. Trả về kết quả tổng số dãy con tìm được.

   Chương trình minh hoạ:

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

long long countZeroSumSubarrays(const vector<int>& A) {
    unordered_map<long long, int> prefixCount; // Lưu số lần xuất hiện của mỗi tổng tiền tố
    prefixCount[0] = 1; // Tổng tiền tố bằng 0 xuất hiện một lần ban đầu

    long long prefixSum = 0; // Tổng tiền tố hiện tại
    long long count = 0; // Số lượng dãy con có tổng bằng 0

    for (int x : A) {
        prefixSum += x; // Cập nhật tổng tiền tố

        // Nếu tổng tiền tố đã xuất hiện, thêm số lần xuất hiện vào count
        if (prefixCount.find(prefixSum) != prefixCount.end()) {
            count += prefixCount[prefixSum];
        }

        // Cập nhật số lần xuất hiện của tổng tiền tố
        prefixCount[prefixSum]++;
    }

    return count;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cout << countZeroSumSubarrays(A) << endl;
    return 0;
}