Hiểu bài toán

Cho một mảng gồm n số nguyên và một số k, nhiệm vụ là đếm số lượng các cặp chỉ số (i, j) sao cho hiệu của hai phần tử arr[i] - arr[j] = k. Với các ràng buộc n < ~10^5, cần một giải pháp hiệu quả hơn O(n^2).

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

Cách Two Pointers (Con trỏ kép)

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
   int n;ll k;cin>>n>>k;ll a[n+1];
   for (int i=1;i<=n;i++) cin>>a[i];
   sort(a+1,a+n+1);
   int l=1,r=1;ll res=0;
    while(r<=n)
    {
        if (a[r]-a[l]==k) {res++;l++;r++;}
        else
            if (a[r]-a[l]>k) l++;
            else r++;
    }
   cout<<res;
}

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

Phương pháp này dựa trên việc sắp xếp mảng tăng dần. Sau đó, sử dụng hai con trỏ (l, r) duyệt từ trái sang phải. Nếu hiệu a[r] - a[l] lớn hơn k, ta cần tăng giá trị hiệu nên tăng l (giảm giá trị trừ). Nếu hiệu nhỏ hơn k, ta cần tăng hiệu nên tăng r (tăng giá trị trừ). Khi hiệu bằng k, ta đếm và di chuyển cả hai con trỏ. Phương pháp này loại bỏ được các cặp không cần thiết trong khi vẫn đảm bảo duyệt qua các cặp có thể tạo thành hiệu k.

Cách Hash Set (Tập hợp băm)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    unordered_set<long long> s;
    long long ans = 0;
    for (long long x : a) {
        if (s.count(x + k)) ans++;
        if (s.count(x - k)) ans++;
        s.insert(x);
    }
    cout << ans << "\n";
}

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

Duyệt qua mảng một lần duy nhất. Với mỗi phần tử x, ta kiểm tra xem có phần tử nào trong tập hợp (chứa các phần tử đã duyệt qua) tạo thành hiệu k với x hay không. Cụ thể, ta cần kiểm tra xem có t tồn tại phần tử có giá trị x + k (nghĩa là x - (x+k) = -k, cần xử lý dấu) hoặc x - k (nghĩa là x - (x-k) = k) hay không. Để đơn giản hóa việc đếm các cặp (i, j) với hiệu arr[i] - arr[j] = k, ta có thể kiểm tra xem arr[j] có trong tập hợp hay không bằng cách tìm arr[i] - k. Nếu có, tăng biến đếm.

Cách Hash Map (Bản đồ băm)

#include <bits/stdc++.h>
using namespace std;
int main() {
    long n, k;
    cin >> n >> k;
    vector<long> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    unordered_map<long,int> cnt;
    for(auto x : a) cnt[x]++;
    long dem = 0;
    for(auto x : a) {
        if(cnt.count(x - k)) dem += cnt[x - k];
    }
    cout << dem;
}

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

Giải pháp này chia làm 2 bước:

1. Đếm tần suất của tất cả các phần tử trong mảng vào một Hash Map.
2. Duyệt lại mảng, với mỗi phần tử x, ta cần tìm số lượng phần tử có giá trị (x - k) để tạo thành cặp (x, y) sao cho x - y = k. Nếu (x - k) t tồn tại trong map, ta cộng dồn số lượng của nó vào biến đếm. Đây là cách tiếp cận trực quan nhất cho bài toán đếm số lượng cặp.

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

Bài học kinh nghiệm

• Hiệu quả của thuật toán phụ thuộc vào việc giảm không gian tìm kiếm từ O(n^2) xuống O(n) hoặc O(n log n).
• Hash Map/Set cho phép kiểm tra sự t tồn tại hoặc đếm số lượng trong thời gian O(1) trung bình.
• Bài toán hiệu k có thể quy về bài toán tìm tổng 2 số bằng k (Two Sum) nếu biến đổi một chút.
• Sắp xếp và hai con trỏ là kỹ thuật chuẩn cho các bài toán mảng liên quan đến hiệu/tổng trên mảng đã sắp xếp.

Lỗi thường gặp

• Quên xử lý số lượng lớn (sử dụng kiểu dữ liệu long long cho biến đếm và các giá trị trong mảng).
• Sử dụng giải pháp O(n^2) dẫn đến Time Limit Exceeded với n ~ 10^5.
• Lỗi logic khi đếm cặp (i, j): nếu không cẩn thận có thể đếm trùng hoặc漏 đếm các cặp (i, j) và (j, i) trong các cách tiếp cận khác nhau. Trong bài này, với Hash Map, ta thường chỉ cần quan tâm đến xu hướng 'tìm phần tử còn thiếu'.
• Trong giải pháp Two Pointers, nếu mảng có số trùng lặp, cần đảm bảo logic di chuyển con trỏ xử lý đúng số lượng cặp (ví dụ: nếu a[l] == a[l+1] và bằng k, cần lặp lại).