[LeetCode] 454. 4Sum II

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

4Sum II - LeetCode

4Sum II

 

기존 Sum 문제에서, 그동안은 하나의 배열에서 수를 골랐다면 

이번 문제에서는 네개의 각기 다른 배열에서 하나씩 수를 골라야한다.

단순하게 4Sum 문제와 비슷하겠다고 생각했으나 그렇지 않고 훨씬 간단했다.

 

배열을 두개씩 두그룹으로 나누자.

첫번째 1,2배열의 모든 합 조합을 Hashmap에 저장해주고 이미 있는 값이면 +1을 해준다. (a1+a2)

그 뒤 두번째 3,4배열의 모든 합 조합을 보고 이에 마이너스를 붙인 값이 Hashmap에 있는지 찾아준다. (a1+a2+a3+a4 = 0 이므로, a1+a2 = -(a3+a4) )

Hashmap에 있다면 결과값에 hashmap 값을 더해준다.

 

전체 풀이 코드

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        map<int, int> m;
        int ret = 0;
        for (int i=0; i<nums1.size(); i++) for (int j=0; j<nums2.size(); j++) m[nums1[i]+nums2[j]]++;
        for (int i=0; i<nums3.size(); i++) for (int j=0; j<nums4.size(); j++) if (m.find(-nums3[i]-nums4[j])!=m.end()) ret+=m[-nums3[i]-nums4[j]];
        return ret;
    }
};