C++で「1つの数が他の2つの数の和として表せる」トリプレットを数える方法

長さ n の整数型配列 Arr[] が与えられます。この記事の目標は、「任意の2つの数の和が残りの1つの数と等しくなる」ようなトリプレット (Arr[i], Arr[j], Arr[k]) の個数を求めることです。

条件は a + b = c で表されます。ここで a、b、c は配列 Arr[] の要素であり、インデックス i、j、k は 0 <= i < j < k < n を満たします。

この問題は、3重の for ループを使って解くことができます。arr[x] + arr[y] = arr[z] かつ x ≠ y ≠ z となる組み合わせが見つかるたびに、カウントを1つ増やしていきます。具体的な例で確認してみましょう。

入力

arr[]= { 1,2,2,3,4 }, N=5

出力

トリプレットの数: 4

説明

arr[x] + arr[y] = arr[z] を満たすトリプレットは以下の通りです。

Arr{}=[ 1,2,2,3,4 ] =(1,2,3) → 1+2=3
Arr{}=[ 1,2,2,3,4 ] =(1,2,3) → 1+2=3（異なるインデックスの組み合わせ）
Arr{}=[ 1,2,2,3,4 ] =(1,3,4) → 1+3=4
Arr{}=[ 1,2,2,3,4 ] =(2,2,4) → 2+2=4

合計トリプレット数: 4

入力

arr[]= {2,2,2,2,2}, N=5

出力

トリプレットの数: 0

説明

どの2つの数を選んでもその和は4になりますが、3番目の数は2であるため条件を満たしません。

合計トリプレット数: 0

プログラムで使用しているアプローチ

• ランダムな整数で初期化された整数型配列 Arr[] を用意します。

• 変数 N には配列 Arr[] の長さを格納します。

• 関数 countTriplets(int arr[], int n) は、配列とその長さを受け取り、「いずれか1つの数が他の2つの数の和として表せる」トリプレットの個数を返します。

• トリプレットの個数を数えるための変数 count を 0 で初期化します。

• 3重の for ループを使って配列を走査し、トリプレットの各要素を順に取り出します。

• 最も外側のループは 0 <= i < n-2、内側のループは i < j < n-1、最も内側のループは j < k < n の範囲で繰り返します。

• arr[i]+arr[j]==arr[k]、または arr[i]+arr[k]==arr[j]、または arr[k]+arr[j]==arr[i] のいずれかが成立する場合、count をインクリメントします。

• すべてのループが終了した時点で、count には条件を満たすトリプレットの総数が格納されています。

• 結果として count を返します。

例

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n){
    int count = 0;
    for (int i = 0; i < n-2; i++){
        for (int j = i+1; j < n-1; j++){
            for (int k = j+1; k < n; k++){
                if(arr[i]+arr[j]==arr[k] || arr[j]+arr[k]==arr[i] || arr[k]+arr[i]==arr[j]){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    int Arr[]={ 1,2,2,3,4 };
    int N=5; //length of array
    cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N);
    return 0;
}

出力

Number of triplets : 4

計算量に関する補足

このアプローチでは3重ループを使用しているため、時間計算量は O(n³) となります。配列のサイズが大きくなると処理時間が急激に増加する点に注意が必要です。より効率的な解法を求める場合は、配列を事前にソートした上でハッシュマップや二分探索を活用する方法などが考えられます。