LeetCode - 454. 4Sum II(Array, Hash Table)*

문제

길이가 n인 정수 배열 nums1, nums2, nums3 및 nums4가 주어지면 다음과 같이 튜플 수(i, j, k, l)를 반환합니다.

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

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

풀이

자바입니다.

• nums1[i]+num2[j] == num3[k]+num4[l] 을 만족하면 됩니다.
• 첫번째 반복문에서 nums1[i], nums2[j] 두 수의합 sum12 모든 경우를 key,
  sum12의 갯수를 value로 map에 넣습니다.
• 두번째 반복문에서 sum12를 찾아야합니다. -(num3[k]+nums4[l]) 을 key로 찾으면 됩니다.
  ex) sum12=2, nums3[k]+nums4[l]=-2 이면 튜플을 만족합니다.
  그래서 nums3[k]+nums4[l] 에 -1을 곱해야 합니다.

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int count = 0;
        
        for(int i: nums1){
            for(int j: nums2){
                int sum12 = i+j;
                map.put(sum12, map.getOrDefault(sum12,0)+1);
            }
        }
        
        for(int i: nums3){
            for(int j: nums4){
                int sum34 = -(i+j);
                count += map.getOrDefault(sum34,0);
            }
        }
        
        return count;
    }
}