ในปัญหานี้ เราจะได้รับอาร์เรย์ของตัวเลขและเราจำเป็นต้องค้นหาแฝดสามที่มี are อยู่ในรูปของการคำนวณทางคณิตศาสตร์
ความก้าวหน้าทางคณิตศาสตร์ คือชุดของตัวเลขที่มีความต่างระหว่างพจน์ที่ต่อเนื่องกัน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า −
Input :
array = {2 , 5 , 7, 8 , 9 , 10}
Output :
2 5 8
5 7 9
7 8 9
8 9 10 ในการแก้ปัญหานี้ วิธีแก้ไขง่ายๆ คือการเรียกใช้สามลูปและตรวจสอบแฝดสามทั้งหมดหากอยู่ใน AP แต่วิธีนี้มีเวลาซับซ้อนของคำสั่ง n 3 .
ทางออกที่ดีกว่าคือการใช้การแฮช ในวิธีนี้ เราจะเริ่มจากองค์ประกอบที่สองของอาร์เรย์ และถือว่าทุกองค์ประกอบเป็นองค์ประกอบกลางของ AP และตรวจสอบว่าองค์ประกอบดังกล่าวเป็น AP หรือไม่
ตัวอย่าง
#include <iostream>
using namespace std;
void TripletsAP(int arr[], int n){
for (int i = 1; i < n - 1; i++){
for (int j = i - 1, k = i + 1; j >= 0 && k < n;){
if (arr[j] + arr[k] == 2 * arr[i]){
cout<<arr[j]<<"\t"<<arr[i]<<"\t"<< arr[k] << endl;
k++;
j--;
}
else if (arr[j] + arr[k] < 2 * arr[i])
k++;
else
j--;
}
}
}
int main(){
int arr[] = {2 , 5 , 7, 8 , 9 , 10};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The triplets that are in AP are : \n";
TripletsAP(arr, n);
return 0;
} ผลลัพธ์
แฝดสามที่อยู่ใน AP คือ −
2 5 8 5 7 9 7 8 9 8 9 10
