สมมติว่าเรามีชุดของจำนวนเต็ม เราต้องหาตัวเลข 'd' ที่ d = a + b + c และเราต้องเพิ่มค่า (a + b + c) ให้มากที่สุด a, b, c และ d ทั้งหมดอยู่ในชุด เซตจะมีอย่างน้อยหนึ่งองค์ประกอบ และสูงสุด 1000 องค์ประกอบ แต่ละองค์ประกอบจะเป็นตัวเลขจำกัด ถ้าชุดคือ {2, 3, 5, 7, 12} แล้ว 12 คือ d ที่ใหญ่ที่สุด สามารถแสดงได้โดย 2 + 3 + 7
เพื่อแก้ปัญหานี้ เราสามารถใช้เทคนิคการแฮช (hashing) เราจะเก็บผลรวมของทุกคู่ของ (a + b) ในตารางแฮช แล้วเดินทางผ่านทุกคู่ (c, d) และค้นหา (d - c) ว่ามีในตารางหรือไม่ หากพบการจับคู่ ให้ตรวจสอบว่าไม่มีองค์ประกอบซ้ำกัน และไม่มีการพิจารณาองค์ประกอบเดียวกันสองครั้ง
ตัวอย่างโค้ด C++
#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
int findElementsInSet(int arr[], int n) {
unordered_map> 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 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;
}
ผลลัพธ์
Max value of d is 12
