Pythonで3つの異なる配列から「a + b + c = sum」となる要素の組み合わせを見つける方法

問題の概要

3つの配列 A、B、C と、目標値「sum」が与えられたとします。このとき、a + b + c = sum を満たす3つの要素 a、b、c が存在するかどうかを判定します。重要な条件として、a、b、c はそれぞれ異なる配列から選ばれる必要があります。

例えば、入力が A = [2,3,4,5,6]、B = [3,4,7,2,3]、C = [4,3,5,6,7]、sum = 12 の場合、出力は True になります。これは 4 + 2 + 6 = 12 が成立し、4、2、6 をそれぞれ A、B、C から取り出せるためです。

解法のアプローチ

この問題は、すべての組み合わせを総当たり（ブルートフォース）で調べることで解決できます。具体的な手順は以下の通りです。

• i を 0 から A のサイズ未満まで繰り返す
• j を 0 から B のサイズ未満まで繰り返す
• k を 0 から C のサイズ未満まで繰り返す
• A[i] + B[j] + C[k] が sum と等しい場合は True を返す

すべての組み合わせを調べても条件を満たす組み合わせが見つからなければ、False を返します。

実装例

以下に Python での実装例を示します。

def is_sum_from_three_arr(A, B, C, total):
    for i in range(0, len(A)):
        for j in range(0, len(B)):
            for k in range(0, len(C)):
                if (A[i] + B[j] + C[k] == total):
                    return True
    return False

A = [2,3,4,5,6]
B = [3,4,7,2,3]
C = [4,3,5,6,7]
total = 12
print(is_sum_from_three_arr(A, B, C, total))

入力

[2,3,4,5,6], [3,4,7,2,3], [4,3,5,6,7], 12

出力

True

計算量と改善のポイント

上記の方法では3重ループを使用しているため、時間計算量は O(n³) となります。各配列のサイズが大きくなると処理時間が急激に増加する点に注意が必要です。

より効率化したい場合は、あらかじめ配列 C の要素をハッシュセット（set）に登録しておき、「sum − A[i] − B[j]」がそのセットに存在するかを O(1) で確認する方法が有効です。これにより、時間計算量を O(n²) まで改善できます。