Pythonでターゲットの合計となる4つの数の組み合わせを数えるプログラム

問題の概要

4つの数値リスト A、B、C、D とターゲット値が与えられたとき、A[i] + B[j] + C[k] + D[l] がターゲットと等しくなるような異なる組（i, j, k, l）の個数を求めることを考えます。

例えば、入力が以下のような場合を想定します。

• A = [5, 4, 3]
• B = [8, 4]
• C = [6, 2]
• D = [4, 10]
• target = 23

このとき出力は 3 となり、条件を満たす組は [5, 8, 6, 4]、[3, 4, 6, 10]、[3, 8, 2, 10] の3つです。

解法のアプローチ

すべての組み合わせを総当たりで調べると計算量が O(n⁴) となり、リストが大きくなると非常に非効率です。そこで、ハッシュマップを活用した効率的な手法を採用します。手順は以下の通りです。

1. カウント変数 count を 0 で初期化する
2. 空のマップ m を用意する
3. A の各要素 i と B の各要素 j について、m[i + j] の値を1ずつ増やす
4. C の各要素 k と D の各要素 z について、target − (k + z) が m に存在すれば、count に m[target − (k + z)] を加算する
5. count を返す

この方法では、A と B のペアの和を事前にマップへ記録しておき、C と D のペアに対して「ターゲットに到達するために必要な残りの値」がマップに存在するかを確認します。これにより、計算量を O(n²) まで抑えることができます。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, A, B, C, D, target):
        count = 0
        from collections import defaultdict

        m = defaultdict(int)
        for i in A:
            for j in B:
                m[i + j] += 1

        for k in C:
            for z in D:
                if target - (k + z) in m:
                    count += m[target - (k + z)]
        return count

ob = Solution()
A = [5, 4, 3]
B = [8, 4]
C = [6, 2]
D = [4, 10]
target = 23
print(ob.solve(A, B, C, D, target))

入力

[5, 4, 3], [8, 4], [6, 2], [4, 10], 23

出力

3

まとめ

collections モジュールの defaultdict を使うことで、キーの存在チェックや初期化を簡潔に扱えます。ハッシュマップを活用することで、4つのリストからターゲットの合計となる組み合わせを効率的に数えられます。素朴な全探索では O(n⁴) かかるところを O(n²) に削減できるのが、この手法の大きな利点です。