【C++】ソート済み配列から等差数列（AP）を形成するすべてのトリプレットを出力する方法

この問題では、ソートされた数値の配列が与えられ、その中から等差数列（AP：Arithmetic Progression）を形成するトリプレット（3つの組）をすべて見つけ出します。

等差数列とは、隣り合う項同士の差（公差）が常に一定である数列のことです。

問題例

入力 :
array = {2 , 5 , 7, 8 , 9 , 10}

出力 :
2 5 8
5 7 9
7 8 9
8 9 10

単純なアプローチ

最もシンプルな解決策は、三重のループを回してすべてのトリプレットを列挙し、それぞれが等差数列を成すかどうかを確認する方法です。しかし、この方法の計算量は O(n³) のオーダーとなり、配列のサイズが大きくなると実用的ではありません。

効率的なアプローチ：中央要素と両ポインターの利用

より効率的なのが、ハッシュや双方向ポインターの考え方を応用した手法です。この方法では、配列の2番目の要素から順に各要素を「等差数列の中央の項」として扱い、次のように探索を行います。

• 中央の項より左側（小さい側）を指すポインター j と、右側（大きい側）を指すポインター k を用意します。
• arr[j] + arr[k] == 2 × arr[i] が成立すれば、3つの値は等差数列を形成しているため、トリプレットとして出力します。
• 合計が 2 × arr[i] より小さい場合は大きな側を進めて k++、大きすぎる場合は小さい側を進めて j-- とし、条件に近づけていきます。

この手法により、三重ループよりも大幅に少ない比較回数で目的のトリプレットをすべて抽出できます。

C++による実装例

#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<<"等差数列を形成するトリプレット : \n";
    TripletsAP(arr, n);
    return 0;
}

実行結果

等差数列を形成するトリプレットは次のとおりです。

2 5 8
5 7 9
7 8 9
8 9 10