[Leetcode(릿코드)] 454. 4SUM 2 (Medium)

leetcode.com/problems/4sum-ii/

4Sum II - LeetCode

---

문제

배열 4개가 주어진다

각 배열의 요소에서 1개씩 뽑아서 모두 더한다

그리고 0이 나오는 경우의 개수를 출력한다

 

예를 들면,

A = [1, 2] B = [-2,-1] C = [-1, 2] D = [0, 2] 이면,

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

 

답은 총 2개이다 

해결

바이너리 서치 문제에서 뽑았는데 바이너리 서치를 이용해서 푸는법은 모르겠다

HashMap을 이용하였다

public static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    int result = 0;

    Map<Integer, Integer> map = new HashMap<>();
    for (int a : A) {
        for (int b : B) {
            int sum = a+b;
            map.put(sum, map.getOrDefault(sum,0)+1);
        }
    }

    for (int c : C) {
        for (int d : D) {
            int sum = c+d;
            result += map.getOrDefault(-1*(sum), 0);
        }
    }

    return result;
}