สมมติว่ามีอาร์เรย์ของตัวเลข n เราต้องหาตัวเลขสามตัว ดังนั้นผลรวมของสององค์ประกอบจะเท่ากับตัวที่สาม ดังนั้นหากอาร์เรย์เป็นแบบ [5, 32, 1, 7, 10, 50, 19, 21, 2] ผลลัพธ์จะเป็น 21, 2, 19 หากไม่พบองค์ประกอบดังกล่าว ให้แสดงข้อความนั้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังต่อไปนี้ −
-
จัดเรียงอาร์เรย์ที่กำหนด
-
จากนั้นเริ่มแก้ไของค์ประกอบที่ยิ่งใหญ่ที่สุดจากองค์ประกอบสุดท้ายและสำรวจอาร์เรย์เพื่อค้นหาตัวเลขอีกสองตัวที่รวมกันเป็นองค์ประกอบที่สาม
-
ใช้ตัวชี้สองตัว j และ k, j มาจากตัวแรก, k มาจากตัวสุดท้ายเพื่อหาค่าที่น้อยที่สุดของสองตัวเลขจาก i - 1 เพื่อหาจำนวนที่ใหญ่ที่สุดของตัวเลขที่เหลือทั้งสองตัว
-
หากการบวกของตัวเลขทั้งสองยังน้อยกว่า Arr[i] เราก็จะต้องเพิ่มค่าของการรวมของตัวเลขสองตัวจึงเพิ่มตัวชี้ j เพื่อเพิ่มมูลค่าของ Arr[j] + Arr[ k]
-
หากการบวกของตัวเลขทั้งสองมากกว่า Arr[i] เราต้องลดค่าของการรวมของตัวเลขสองตัวลง ซึ่งจะทำให้ตัวชี้ k ลดลง ซึ่งจะลดค่าโดยรวมของ Arr[j] + Arr[k ]
ตัวอย่าง
#include<iostream>
#include<algorithm>
#define N 5
using namespace std;
void getValueTriplet(int arr[], int n) {
sort(arr, arr + n);
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
while (j < k) {
if (arr[i] == arr[j] + arr[k]) {
cout << "The numbers are " << arr[i] << " " << arr[j] << " " << arr[k] << endl;
return;
}
else if (arr[i] > arr[j] + arr[k])
j += 1;
else
k -= 1;
}
}
cout << "No such triplet exists";
}
int main() {
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
getValueTriplet(arr, n);
} ผลลัพธ์
The numbers are 21 2 19
