พิมพ์ Triplets ใน Sorted Array ที่เป็น AP ใน C++

ในปัญหานี้ เราจะได้รับ sorted array ของตัวเลข และต้องหา triplets ที่อยู่ในรูป arithmetic progression

Arithmetic Progression คือ ชุดของตัวเลขที่ความต่างระหว่างพจน์ติดกันเท่ากัน

ตัวอย่างเพื่อความเข้าใจ

Input: array = {2, 5, 7, 8, 9, 10}
Output: 2 5 8 5 7 9 7 8 9 8 9 10

เพื่อแก้ปัญหานี้ วิธีง่ายคือรัน 3 loops ตรวจสอบทุก triplets ว่าเป็น AP หรือไม่ แต่ time complexity เป็น O(n³)

วิธีที่ดีกว่าคือใช้ hashing ในวิธีนี้ เราจะเริ่มจากองค์ประกอบตัวที่ 2 ของ array และถือว่าทุกองค์ประกอบเป็น middle element ของ 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;
}

ผลลัพธ์

The triplets that are in AP are -