LeetCode: 4Sum 2

주어진 4개의 배열의 원소들을 조합해서 0이 되는 갯수를 구하는 문제이다.

문제 풀이

원소들의 조합을 구해야하므로 다중 for문을 돌려야한다고 생각했다.
한번데 4중 for문을 돌리자니 이건 아니라 싶었고, 쪼개서 돌리기로 했다.
우선 4개의 원소의 합이 0인 종류를 return하면 되므로 배열을 2개씩 짝지어 생각하기로 했다.
A[i], B[j]를 합한 값을 hashmap에 (합한 값, 갯수)를 저장했다.
C[i], D[j]를 합한 값이 -(A[i] + B[j])와 같으면 4개를 합한 값이 0이다.
위와 같은 flow로 문제를 풀었다.

import java.util.*;
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        if(A.length == 0) {
            return 0;
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = A.length;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                int temp = A[i] + B[j];
                if(map.containsKey(temp)) {
                map.put(temp, map.get(temp) + 1);
            }
            else {
                map.put(temp, 1);
            }
            }
        }
        int answer = 0;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                int temp = C[i] + D[j];
                temp *= -1;
                if(map.containsKey(temp)) {
                    answer += map.get(temp);
                }
            }
        }
        return answer;
    }
}