454. 4Sum II - python3

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2^28 to 2^28 - 1 and the result is guaranteed to be at most 2^31 - 1.

My Answer 1: Time Limit Exceeded (21 / 48 test cases passed.)

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        listA = []
        listB = []
        
        for i in A:
            for j in B:
                listA.append(i+j)
        for i in C:
            for j in D:
                listB.append(i+j)
                
        count = 0
        for i in listA:
            for j in listB:
                if i+j == 0:
                    count += 1
                    
        return count

A, B 의 합과 C, D 의 합을 더한 값이 0 이면 count 하도록 함
하지만 타임 리밋~~~

My Answer 2: Accepted (Runtime: 276 ms - 74.09% / Memory Usage: 60.4 MB - 24.53%)

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        listA = collections.defaultdict(int)
        listB = collections.defaultdict(int)
        
        for i in A:
            for j in B:
                listA[i+j] += 1
        for i in C:
            for j in D:
                listB[i+j] += 1
                
        count = 0
        
        for i in listA:
            if -i in listB:
                count += listA[i] * listB[-i]
                    
        return count

아무래도 list 가 느린 거 같아서 hash 와 비슷한 역할을 하는 defaultdict 딕셔너리를 이용했다

1. A 와 B 의 합을 인덱스로 갖는 list 의 값에 1씩 더해줌 + C 와 D 도 마찬가지

2. "listA 값 - listB 의 값 = 0" 이 되어야하고 이는 곧 "-(listA 의 값) = listB 의 값" 이므로

3. -(listA 의 값)이 listB 에 있으면 두 개의 key 값을 곱해서 더해준다 (경우의 수)

답을 참고해서 직접 짜봤읍니다^^