Lời giải: Perfect Pair (Cặp Hoàn Hảo)

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

Bài toán yêu cầu đếm số cặp chỉ số \((i, j)\) với \(i < j\) sao cho \(a_i + a_j = K\).

Cách tiếp cận tối ưu

1. Sử dụng một bảng băm (std::unordered_map<long long, int> hoặc std::map<long long, int>) để lưu tần suất xuất hiện của các phần tử đã duyệt qua.
2. Khi duyệt đến phần tử \(a_j\), số lượng phần tử \(a_i\) (\(i < j\)) thỏa mãn \(a_i + a_j = K \iff a_i = K - a_j\) chính là giá trị cnt[K - a_j].
3. Cộng cnt[K - a_j] vào kết quả và cập nhật cnt[a_j]++.

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

• Thời gian: \(O(N \log N)\) (khi dùng std::map) hoặc \(O(N)\) trung bình (khi dùng std::unordered_map).
• Không gian bộ nhớ: \(O(N)\) để lưu trữ bảng băm.

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

#include <iostream>
#include <vector>
#include <unordered_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;

    vector<long long> a(n);
    unordered_map<long long, int> cnt;
    long long ans = 0;

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

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