[LeetCode][Python3] 454. 4Sum II

Problem :

https://leetcode.com/problems/4sum-ii/

My Solution :

class Solution:

def fourSumCount(self, A, B, C, D):

"""

:type A: List[int]

:type B: List[int]

:type C: List[int]

:type D: List[int]

:rtype: int

"""

ans = 0

ab = {}

for a in A:

for b in B:

ab[a+b] = ab.get(a+b, 0) + 1

for c in C:

for d in D:

ans += ab.get(-c-d, 0)

return ans

Comment :

길이가 최대 500이라 가정하면 4중 for문을 사용했을 때 625억가지 경우의 수가 나온다. 하지만 2개씩 묶으면 각각 25만개가 최대이다. 625억번 계산은 매우 느리지만 25만번 계산을 두번 반복하는건 충분히 해볼만하다.