C++で指定された差分を持つペアを見つける方法

はじめに

配列 A に n 個の異なる要素が格納されているとします。この配列から、2つの要素 x と y の差が指定された値 d と一致するようなペア (x, y) をすべて見つける必要があります。

例として、配列が A = [10, 15, 26, 30, 40, 70]、指定された差分が 30 である場合を考えます。このとき、該当するペアは (10, 40) と (40, 70) です。

解法：ツーポインタ法

この問題は、配列が昇順にソートされていることを前提とすれば、ツーポインタ（二重インデックス）法を使って効率的に解くことができます。まず、1つ目のポインタ「i」を先頭の要素に、2つ目のポインタ「j」を2番目の要素に設定します。

その後、次のルールに従ってポインタを動かしていきます。

• A[j] − A[i] が n と等しい場合：そのペアを出力し、i と j をそれぞれ1つ進めます。
• A[j] − A[i] が n より小さい場合：差を広げるために j を1つ進めます。
• A[j] − A[i] が n より大きい場合：差を縮めるために i を1つ進めます。

この処理を、どちらかのポインタが配列の末尾に到達するまで繰り返します。

サンプルコード

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

実行結果

(10, 40)
(40, 70)

計算量

• 時間計算量：O(n) — 配列を一度だけ走査するため、線形時間で処理できます。
• 空間計算量：O(1) — ポインタ2つ分の追加メモリのみで動作します。

まとめ

ソート済み配列に対してツーポインタ法を用いることで、指定された差分を持つペアを O(n) の時間計算量で効率的に見つけることができます。ハッシュセットを利用する方法もありますが、追加メモリをほとんど必要としない点で、この方法が有利です。