[LeetCode/Medium] 454. 4Sum II

1. Input

1) int[] nums1

2) int[] nums2

3) int[] nums3

4) int[] nums4

 

2. Output

1) 각 배열에서 1개씩 뽑아 만든 네 수의 합이 0이 되는 순서쌍의 개수를 반환

 

3. Constraint

1) n == nums1.length == nums2.length == nums3.length == nums4.length

2) 1 <= n <= 200

3) - 2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

 

4. Example

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

설명:

- nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0

- nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

 

5. Code

1) 첫 코드(2023/02/22)

int answer = 0;
HashMap<Integer,Integer> m1 = new HashMap<Integer,Integer>();
for(int a : nums1){
    for(int b : nums2){
        if(m1.containsKey(a+b)) m1.put(a+b, m1.get(a+b)+1);
        else m1.put(a+b, 1);
    }
}
HashMap<Integer,Integer> m2 = new HashMap<Integer,Integer>();
for(int a : nums3){
    for(int b : nums4){
        if(m2.containsKey(a+b)) m2.put(a+b, m2.get(a+b)+1);
        else m2.put(a+b, 1);
    }
}
Iterator it = m1.keySet().iterator();
while(it.hasNext()){
    int a = (int)it.next();
    if(m2.containsKey(-a))
        answer += (int)m1.get(a) * (int)m2.get(-a);
}
return answer;

- 반복횟수를 줄여보고자 2개로 나눠서 짜봤는데, 역시나 성능이 별로다.