C++で配列内の合計が指定範囲[a, b]に収まるトリプレットの数を数える方法

問題の概要

整数型の配列 Arr[] と、範囲を定義する2つの変数 a・b が与えられます。この記事の目的は、3つの要素の合計が範囲 [a, b] の間に収まるトリプレット（3要素の組み合わせ）の個数を求めることです。

解法には3重の for ループを使用します。arr[i] + arr[j] + arr[k] が a 以上かつ b 以下を満たすたびにカウントを1増やします。添字の範囲は 0 <= i <= n-2、i < j < n-1、j < k < n です。ここで n は配列 Arr[] の要素数を表します。

具体例で確認してみましょう。

入力例1

入力 − arr[] = { 1, 2, 3, 4, 5 }, N = 5, L = 2, R = 8

出力 − トリプレットの数 − 4

説明 −

合計が2以上8以下のトリプレット
(1,2,3) → 6
(1,2,4) → 7
(1,2,5) → 8
(1,3,4) → 8
合計: 4個

入力例2

入力 − arr[] = { 2, 2, 2, 2, 2 }, N = 5, L = 2, R = 5

出力 − トリプレットの数 − 0

説明 −

すべてのトリプレットの合計は6となり、範囲 [2, 5] には含まれません。

合計: 0個

プログラムで使用するアプローチ

• ランダムな数値で初期化した整数型配列 Arr[] を用意します。
• 範囲 [L, R] を定義するための変数 L と R を用意し、N には配列 Arr[] の長さを格納します。
• 関数 countTriplets(int arr[], int n, int a, int b) は、配列・その長さ・範囲の変数を引数として受け取り、合計が範囲内に収まるトリプレットの数を返します。
• トリプレットの個数を数えるための変数 count を 0 で初期化します。
• 各トリプレットの合計を格納する変数 sum を用意します。初期値は 0 です。
• トリプレットの各要素に対応する3重の for ループで配列を走査します。
• 最も外側のループは 0 <= i < n-2、内側のループは i < j < n-1、最も内側のループは j < k < n となります。
• sum = arr[i] + arr[j] + arr[k] を計算し、a <= sum <= b であれば count をインクリメントします。
• すべてのループが終わった時点で、count には条件を満たすトリプレットの総数が格納されています。
• 最後に count を結果として返します。

なお、この手法は3重ループを使用するため計算量は O(n³) となります。小〜中規模の配列には十分実用的ですが、より大きな入力に対してはソートや二分探索を組み合わせた高速化も検討するとよいでしょう。

実装例

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n, int a, int b){
    int count = 0;
    int sum = 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++){
                sum = arr[i] + arr[j] + arr[k];
                if (sum >= a && sum <= b){ // 範囲内かどうかを判定
                    count++;
                    // cout << endl << "a :" << arr[i] << " b :" << arr[j] << " c :" << arr[k]; // 表示用
                }
            }
        }
    }
    return count;
}
int main(){
    int Arr[] = { 5, 4, 3, 6, 8, 2 };
    int L = 9;
    int R = 15;
    int N = 6; // 配列の長さ
    cout << endl << "トリプレットの数 : " << countTriplets(Arr, N, L, R);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます −

トリプレットの数 : 14