[Leet] - 454. 4Sum II[hash] - c++
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;
}
};
Author And Source
이 문제에 관하여([Leet] - 454. 4Sum II[hash] - c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mopevxw/Leet-454.-4Sum-IIhash-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)