[LeetCode.454][middle] 4Sum II

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

4Sum II - LeetCode

 

초기 접근 방법

일단 브루트포스 알고리즘으로 접근했다.

모든 경우의 수를 4중 for loop 돌려서 전체를 탐색했다.

테스트케이스는 통과했지만, 시간초과 에러로 실패했다.

 

초기 코드

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int ans=0;
        
        for(auto n1:nums1) {
            for(auto n2:nums2) {
                for(auto n3:nums3) {
                    for(auto n4:nums4) {
                        if(n1+n2+n3+n4==0) {
                            ans+=1;
                        }
                    }
                }
            }
        }
        
        return ans;
    }
};

 

알고리즘 보정

초기 접근 방식은 O(n^4)의 시간복잡도를 갖는다. 추가적인 공간은 필요없지만 너무나도 느린 속도의 알고리즘이다.

고민하다가 hash map을 이용하면 시간복잡도를 낮출 수 있을거라 생각했고,

Discuss의 다른 분 풀이를 참고하여 아래와 같이 O(n^4)의 시간복잡도를 가지는 알고리즘으로 풀 수 있었다. 

 

풀이 코드

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> hashmap;
        int ans=0;
        
        for(auto n1:nums1) {
            for(auto n2:nums2) {
                hashmap[n1+n2]+=1;
            }
        }
        
        for(auto n3:nums3) {
            for(auto n4:nums4) {
                ans+=hashmap[-n3-n4];
            }
        }
        
        return ans;
    }
};