[LeetCode] 454. 4Sum II

😎풀이

1. nums1과 nums2의 합산 결괏값과 빈도를 미리 매핑하여 저장
2. nums3와 nums4의 합산 결괏값을 0으로 만들 수 있는 값 탐색
3. n의 4제곱의 시간 복잡도에서 n제곱의 시간 복잡도로 탐색한 경우의 수 반환

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    const n = nums1.length
    let count = 0
    const sums = new Map<number, number>()
    for(const num1 of nums1) {
        for(const num2 of nums2) {
            const sum = num1 + num2
            sums.set(sum, (sums.get(sum) ?? 0) + 1)
        }
    }
    for(const num3 of nums3) {
        for(const num4 of nums4) {
            const sum = -(num3 + num4)
            if(!sums.has(sum)) continue
            count += sums.get(sum)
        }
    }
    return count
};