Tìm cặp phần tử với hiệu số cho trước trong C++

Cho một mảng A chứa n phần tử khác nhau. Bài toán yêu cầu tìm một cặp (x, y) từ mảng A sao cho hiệu giữa x và y bằng một giá trị cho trước d. Ví dụ, với mảng A = [10, 15, 26, 30, 40, 70] và hiệu d = 30, ta sẽ tìm được các cặp (10, 40) và (30, 70).

Giải thuật

Giả sử mảng đã được sắp xếp. Ta sử dụng kỹ thuật hai con trỏ: con trỏ i trỏ đến phần tử đầu tiên, con trỏ j trỏ đến phần tử thứ hai. Nếu A[j] - A[i] bằng d, in ra cặp và tăng cả i, j. Nếu hiệu nhỏ hơn d, tăng j. Ngược lại, tăng i.

Ví dụ minh họa

#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);
}

Kết quả

(10, 40)
(30, 70)