[LeetCode] 454. 4Sum II, Medium

1. 문제

• 배열 4개가 주어질 때, 각 요소의 합이 0이되는 튜플의 수 를 구하라.

2. 해결

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    const map = new Map<number, number>();
    const n = nums1.length;

    let ans = 0;

    for(let i =0; i< n;i++) {
        for(let j=0; j<n;j++) {
            map.set(nums1[i] + nums2[j], (map.get(nums1[i] + nums2[j]) ?? 0) +1)
        }
    }

    for(let i =0; i< n;i++) {
        for(let j=0; j<n;j++) {
            ans += map.get(-(nums3[i] + nums4[j])) ?? 0;        
        }
    }

    return ans;
};

• 4개의 배열이기 때문에 모든 경우의 수를 탐색하면 당연히 시간 초과가 날 것.
• 근데 못풀었다.
• 접근 방식이 안떠오른다 도저히.
• map을 이용해서 2개의 배열씩 등장할 수 있는 값과 등장 회수를 key-value로 관리
• 다른 2개의 배열을 이용해 -를 붙여 해당 key가 있으면 등장 회수를 더해준다.