หาสามตัวเลขที่ผลรวมของสองตัวเท่าตัวที่สามใน C++

โจทย์

ให้อาร์เรย์ของตัวเลข n ตัว ต้องการหา 3 ตัวเลข ที่ผลรวมของ 2 ตัวเท่ากับตัวที่ 3

ตัวอย่าง: [5, 32, 1, 7, 10, 50, 19, 21, 2] → ผลลัพธ์: 21, 2, 19 (เพราะ 2 + 19 = 21)

วิธีแก้ปัญหา (Two Pointers)

1. เรียงอาร์เรย์จากน้อยไปมาก
2. ลูป i จากท้ายสุด (ค่ามากที่สุด) กลับมาหาหัว
3. สำหรับแต่ละ i ใช้ two pointers: j เริ่มต้นที่ 0, k เริ่มต้นที่ i-1
4. ถ้า arr[j] + arr[k] == arr[i] → เจอคำตอบ
5. ถ้า arr[j] + arr[k] < arr[i] → เพิ่ม j (เพิ่มผลรวม)
6. ถ้า arr[j] + arr[k] > arr[i] → ลด k (ลดผลรวม)

ตัวอย่างโค้ด C++

#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