Giả sử chúng ta có một tập hợp các số nguyên. Chúng ta phải tìm một số ‘d’, trong đó d =a + b + c, và chúng ta phải cực đại (a + b + c), tất cả a, b, c và d đều có mặt trong tập hợp. Tập hợp sẽ chứa ít nhất một phần tử và tối đa 1000 phần tử. Mỗi phần tử sẽ là một số hữu hạn. Nếu tập hợp là {2, 3, 5, 7, 12} thì 12 lớn nhất d. điều này có thể được biểu thị bằng 2 + 3 + 7
Để giải quyết vấn đề này, chúng ta có thể sử dụng kỹ thuật băm. Chúng ta sẽ lưu trữ tổng của tất cả các cặp (a + b) trong bảng băm, sau đó duyệt qua tất cả các cặp (c, d) và tìm kiếm (d - c) có trong bảng hay không. Nếu tìm thấy một kết quả trùng khớp, thì hãy đảm bảo rằng không có hai phần tử nào giống nhau và không phần tử nào giống nhau được xem xét hai lần.
Ví dụ
#include<iostream>
#include<unordered_map>
#include<climits>
using namespace std;
int findElementsInSet(int arr[], int n) {
unordered_map<int, pair<int, int> > table;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
table[arr[i] + arr[j]] = { i, j };
int d = INT_MIN;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int abs_diff = abs(arr[i] - arr[j]);
if (table.find(abs_diff) != table.end()) {
pair<int, int> p = table[abs_diff];
if (p.first != i && p.first != j && p.second != i && p.second != j) d = max(d, max(arr[i], arr[j]));
}
}
}
return d;
}
int main() {
int arr[] = { 2, 3, 5, 7, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
int res = findElementsInSet(arr, n);
if (res == INT_MIN)
cout << "Cannot find the value of d";
else
cout << "Max value of d is " << res;
} Đầu ra
Max value of d is 12