Giả sử chúng ta có một danh sách các số nguyên. Nhiệm vụ là tìm bốn số nguyên riêng biệt thành hai cặp (a, b) và (c, d) sao cho a+b = c+d. Nếu có nhiều câu trả lời, chỉ in một cặp. Ví dụ mảng A = [7, 5, 9, 3, 6, 4, 2], thì các cặp có thể là (7, 3) và (6, 4).
Ở đây chúng ta sử dụng kỹ thuật hashing. Sử dụng tổng làm khóa và cặp làm giá trị trong bảng băm. Các bước giải quyết như sau:
- Với i từ 0 đến n-1, thực hiện:
- Với j từ i+1 đến n-1, thực hiện:
- Tính tổng.
- Nếu bảng băm đã có tổng đó, in cặp trước đó và cặp hiện tại.
- Ngược lại, cập nhật bảng băm.
Ví dụ
#include<iostream> #include<map> using namespace std; bool getTwoPairs(int arr[], int n) { map<int, pair<int, int> > hash_table; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int sum = arr[i] + arr[j]; if (hash_table.find(sum) == hash_table.end()) hash_table[sum] = make_pair(i, j); else { pair<int, int> pp = hash_table[sum]; cout << "(" << arr[pp.first] << " + " << arr[pp.second] << ") = (" << arr[i] << " + " << arr[j] << ")"; return true; } } } cout << "No pairs found"; return false; } int main() { int arr[] = {7, 5, 9, 3, 6, 4, 2}; int n = sizeof arr / sizeof arr[0]; cout << "The pairs are: "; getTwoPairs(arr, n); }
Kết quả
The pairs are: (7 + 4) = (5 + 6)