หาคู่ของตัวเลขที่มีความต่างเท่ากับค่าที่กำหนดใน C++

ปัญหา

ให้อาร์เรย์ A ที่มี n สมาชิกที่แตกต่างกัน ต้องการหาคู่ (x, y) จากอาร์เรย์ A ที่ทำให้ความต่างระหว่าง x และ y เท่ากับค่าความต่าง d ที่กำหนดไว้

ตัวอย่าง: A = [10, 15, 26, 30, 40, 70] และ d = 30 คู่ที่ได้คือ (10, 40) และ (30, 70)

วิธีแก้ปัญหา

สมมติว่าอาร์เรย์ได้รับการจัดเรียงแล้ว ใช้เทคนิค Two Pointers:

• Pointer i ชี้ที่สมาชิกแรก (index 0)
• Pointer j ชี้ที่สมาชิกที่สอง (index 1)
• ถ้า A[j] - A[i] == d พบคู่ที่ต้องการ พิมพ์คู่ และเพิ่ม i, j ทั้งคู่
• ถ้า A[j] - A[i] < d เพิ่ม j ขึ้น 1
• ถ้า A[j] - A[i] > d เพิ่ม i ขึ้น 1

ทำซ้ำจนกว่า i หรือ j จะถึงขอบเขตอาร์เรย์

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

#include <iostream>
using namespace std;

void displayPair(int arr[], int size, int n) {
    int i = 0;
    int j = 1;
    while (i < size && j < size) {
        if (i != j && arr[j] - arr[i] == n) {
            cout << "(" << arr[i] << ", " << arr[j] << ")" << endl;
            i++; j++;
        }
        else if (arr[j] - arr[i] < n)
            j++;
        else
            i++;
    }
}

int main() {
    int arr[] = {10, 15, 26, 30, 40, 70};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 30;
    displayPair(arr, size, n);
    return 0;
}

ผลลัพธ์

(10, 40)
(30, 70)