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만번 계산을 두번 반복하는건 충분히 해볼만하다.