[Leet] - 454. 4Sum II[hash] - c++

mopevxw·2022년 2월 8일
0

LeetCode

목록 보기
18/21

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

c++ unordered_map 풀이

시간제한 해결 위해 nums1,nums2 / nums3,nums4 각각으로 O(n^2)시간 복잡도
1. 처음 두 배열에 대해 unordered_map에 <합,등장횟수>로 저장
2. 다음 두 배열에 대해 unordered_map에 -합의 등장 횟수를 answer에 더한다.

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map <int,int> mp;
        int ans =0;
        
        for(int i=0;i<nums1.size();i++)
        {
            for(int j=0;j<nums2.size();j++)
            {
                mp[nums1[i]+nums2[j]]++;
            }
        }
        
        for(int i=0;i<nums3.size();i++)
        {
            for(int j=0;j<nums4.size();j++)
            {
                ans+=mp[-(nums3[i]+nums4[j])];
            }
        }
        
        return ans;
        
    }
};

0개의 댓글