สมมติว่ามีรายการจำนวนเต็ม งานของเราคือการหาจำนวนเต็ม 4 ตัวที่แตกต่างกัน เป็นสองคู่ เช่น (a, b) และ (c, d) ซึ่ง a+b = c+d หากมีคำตอบหลายคำตอบ ให้พิมพ์เพียงคำตอบเดียว สมมติว่าองค์ประกอบอาร์เรย์คือ A = [7, 5, 9, 3, 6, 4, 2] คู่ที่เป็นไปได้คือ (7, 3) และ (6, 4)
ที่นี่เราจะใช้เทคนิคการแฮช (Hashing) เราใช้ผลรวมเป็นคีย์ (Key) และคู่เป็นค่า (Value) ในตารางแฮช เราต้องทำตามขั้นตอนเหล่านี้เพื่อแก้ปัญหานี้:
- สำหรับ i ในช่วง 0 ถึง n – 1 ทำ
- สำหรับ j ในช่วง i + 1 ถึง n – 1 ทำ
- หาผลรวม
- ถ้าตารางแฮชมีผลรวมนี้อยู่แล้ว ให้พิมพ์คู่ก่อนหน้าและคู่ปัจจุบัน
- มิฉะนั้น ให้อัปเดตตารางแฮช
- สำหรับ j ในช่วง i + 1 ถึง n – 1 ทำ
ตัวอย่าง
#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);
}
ผลลัพธ์
The pairs are: (7 + 4) = (5 + 6)
