# LeetCode Medium 454. 4Sum II

tags: leetcode

問題

• Explore
• Problems

アイデア

整数列A，B，C，Dが与えられるとき，それぞれの要素を1つずつ取り出してその総和が0となるようなものは何通り考えられるかを答えろという問題です．

ナイーブに解こうとすると$O(N⁴)$が必要ですが，連想配列を使うことで答えを記録すれば計算量を落とせそうです．

解法

• AとBの要素の組み合わせを全探索し，その値をkeyとして，登場回数をvalueとする連想配列を作ります．
• 次にCとDの要素の組み合わせを全探索します．
  • a + b + c + dであれば，a + b = -c - dであるので，CとDの要素の和を負にしたものを連想配列がkeyに持つならば，その登場回数を答えに加えれば良いです．

計算量

配列の最大長を$N$とします．

• 時間計算量
  • $O(N²)$
• 空間計算量
  • $O(N²)$

Python

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        complement_dic = {}
        res = 0
        for a in A:
            for b in B :
                if a + b in complement_dic:
                    complement_dic[a+b] += 1
                else :
                    complement_dic[a+b] = 1
        for c in C :
            for d in D :
                if -c - d in complement_dic:
                    res += complement_dic[-c-d]
        return res