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 cặp chỉ số (i, j) sao cho i < j và a[i] + a[j] = K. Đây là bài toán kinh điển về tìm cặp số có tổng bằng K.

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

Cách Brute Force (Lặp kép)

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

int main() {
    ifstream cin("SUMX.INP");
    ofstream cout("SUMX.OUT");

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

    long long count = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(a[i] + a[j] == k) {
                count++;
            }
        }
    }

    cout << count;
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

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 cặp (i, j) với i < j. Với mỗi cặp, ta kiểm tra xem tổng của chúng có bằng K hay không. Đây là cách làm trực quan nhất nhưng hiệu quả không cao.

Cách Hash Map (Băm)

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

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

    freopen("SUMX.INP", "r", stdin);
    freopen("SUMX.OUT", "w", stdout);

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

    unordered_map<int, long long> freq;
    long long countPairs = 0;

    for (int i = 0; i < n; i++) {
        int need = k - a[i];
        // Nếu phần tử 'need' đã xuất hiện trước đó,
        // ta có thể tạo thành cặp với các lần xuất hiện trước đó
        if (freq.find(need) != freq.end()) {
            countPairs += freq[need];
        }
        freq[a[i]]++;
    }
    cout << countPairs;
    return 0;
}

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

Sử dụng một hash map (unordered_map) để lưu tần suất xuất hiện của các số. Duyệt mảng một lần, với mỗi phần tử a[i], ta tính phần tử cần thiết là need = K - a[i]. Nếu need đã xuất hiện trong map, số lượng cặp mới tạo ra bằng tần suất của need. Sau đó cập nhật tần suất của a[i].

Cách Hashing (Dùng mảng)

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

const int MAX_VAL = 100000;
int cnt[MAX_VAL + 1];

int main() {
    freopen("SUMX.INP", "r", stdin);
    freopen("SUMX.OUT", "w", stdout);

    int n, k;
    cin >> n >> k;

    long long d = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int need = k - x;
        if (need >= 0 && need <= MAX_VAL) {
            d += cnt[need];
        }
        cnt[x]++;
    }
    cout << d;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1) (phụ thuộc vào giới hạn giá trị phần tử)

Đây là biến thể của Hash Map nhưng sử dụng mảng thường (array) thay vì cấu trúc dữ liệu phức tạp. Nó hiệu quả hơn về tốc độ truy cập và bộ nhớ nếu giá trị của các phần tử nằm trong một khoảng nhỏ và xác định trước (ví dụ 1 đến 100,000).

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

Bài học kinh nghiệm

• Bài toán đếm cặp có tổng bằng K có thể giải quyết trong thời gian tuyến tính O(N) bằng cách sử dụng cấu trúc dữ liệu băm (Hash Map/Mảng).
• Một cách tiếp cận khác là sắp xếp mảng và sử dụng kỹ thuật Hai con trỏ (Two Pointers), nhưng Hashing thường nhanh hơn và dễ cài đặt hơn trong trường hợp này.

Lỗi thường gặp

• Quên kiểm tra điều kiện i < j (tránh đếm trùng hoặc đếm một phần tử với chính nó nếu K chẵn). Trong cách tiếp cận Hash Map, việc duyệt từ trái sang phải và chỉ cộng tần suất của phần tử đang xét sau khi kiểm tra 'need' đảm bảo điều kiện này.
• Lỗi tràn số nguyên khi tính tổng hoặc nhân tần suất (sử dụng kiểu dữ liệu long long cho biến đếm).
• Trong phương pháp Brute Force, nếu N lớn (ví dụ > 10,000) thì chương trình sẽ bị TLE (Time Limit Exceeded).