LeetCode 풀기 - 454. 4Sum II

454. 4Sum II

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

4Sum II - LeetCode

문제)

솔루션1) brute-force

O(n^4)으로 풀었더니 역시나 TLE(Time Limit Exceeded) 발생합니다.

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        count = 0
        for n1 in nums1:
            for n2 in nums2:
                for n3 in nums3:
                    for n4 in nums4:
                        if (n1 + n2 + n3 + n4) == 0:
                            count +=1
        return count

솔루션2) HashMap

O(n^4) 시간 복잡도를 O(n^2)로 줄여서 문제를 풀어봅니다.

두 그룹으로 나누어서 계산을 하는 방식입니다.

 

첫 번째 그룹에서는 sum을 계산해서 hash에 키로 sum 값을 저장하고 value에는 count를 저장합니다.

두 번째 그룹에서는 첫 번째 그룹과의 sum이 0을 만들어 내는 sum을 -sum을 찾아서 count를 더해서 찾는 방식입니다.

 

설명이 더 어렵네요. 코드를 보는 것이 더 이해하기 쉬울 것입니다.

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        """
        Time Complexity : O(2n^2)
        """
        
        d = defaultdict(int)      
        for n1 in nums1:
            for n2 in nums2:
                d[n1+n2] += 1
        
        
        count = 0
        
        # nums1 + nums2 + nums3 + nums4 = 0 --> nums1 + nums2 = -(nums3+ nums4)
        for n3 in nums3:
            for n4 in nums4:
                count += d[-(n3+n4)]
        return count

 

Counter 객체 사용

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        c = Counter([n1+n2 for n1 in nums1 for n2 in nums2])
        return sum(c[-n3-n4] for n3 in nums3 for n4 in nums4)