Pythonで解く4Sum II|4つのリストから合計が0になる組み合わせを数える方法

問題の概要

整数値を持つ4つのリスト A、B、C、D が与えられたとき、A[i] + B[j] + C[k] + D[l] がゼロになるようなタプル (i, j, k, l) の個数を求めるのがこの問題です。

すべてのリストは同じ長さ N(0 ≤ N ≤ 500)を持ち、各整数は −2²⁸ から 2²⁸ − 1 の範囲に収まります。また、答えは最大でも 2³¹ − 1 であることが保証されています。

具体例

たとえば、入力が A = [1, 2]、B = [-2, -1]、C = [-1, 2]、D = [0, 2] の場合、出力は 2 になります。条件を満たすタプルは次の2つです。

• (0, 0, 0, 1):A[0] + B[0] + C[0] + D[1] = 1 + (−2) + (−1) + 2 = 0
• (1, 1, 0, 0):A[1] + B[1] + C[0] + D[0] = 2 + (−1) + (−1) + 0 = 0

解法のアプローチ

4つのリストすべての組み合わせを総当たりで調べると、計算量は O(N⁴) となり非常に非効率です。そこで、リストを2組のペア(A・B と C・D)に分けて考えることで、計算量を O(N²) まで削減できます。

具体的な手順は以下の通りです。

1. A と B の要素の和を記録するためのマップ(辞書)sums を用意します。
2. A の各要素 i と B の各要素 j について、和 i + j をキーとして出現回数をマップに記録します。
   • i + j がマップに存在しない場合は sums[i + j] = 1 を設定
   • すでに存在する場合は sums[i + j] を 1 増加させる
3. カウンター counter を 0 で初期化します。
4. C の各要素 i と D の各要素 j について、−(i + j) がマップに存在すれば、対応する出現回数を counter に加算します。
5. 最後に counter を返します。

実装例(Python)

以下のコードで実際の実装を確認できます。

class Solution(object):
    def fourSumCount(self, A, B, C, D):
        sums = {}
        for i in A:
            for j in B:
                if i+j not in sums:
                    sums[i+j] = 1
                else:
                    sums[i+j] += 1
        counter = 0
        for i in C:
            for j in D:
                if -1 * (i+j) in sums:
                    counter += sums[-1*(i+j)]
        return counter

ob1 = Solution()
print(ob1.fourSumCount([1,2], [-2,-1], [-1,2], [0,2]))

入力

[1,2]
[-2,-1]
[-1,2]
[0,2]

出力

2

計算量の評価

• 時間計算量:O(N²) — A×B と C×D の組み合わせをそれぞれ一度ずつ調べるだけで済みます。
• 空間計算量:O(N²) — A と B の和の全組み合わせをマップに保存するためです。

N が最大 500 の場合でも、O(N²) なら約25万回の処理で完了するため、総当たりの O(N⁴)(約625億回)と比べて圧倒的に高速です。ハッシュマップによる検索は平均 O(1) で行えるため、この手法は大規模な入力にも十分対応できます。