454. 4Sum II

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int n = A.length;
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    for (int l = 0; l < n; l++) {
                        if (A[i] + B[j] + C[k] + D[l] == 0) {
                            result++;
                        }
                    }
                }
            }
        }
        
        return result;
    }
}

Time Limit Exceeded
전씨 저와 같은 생각 했을거라고 믿읍니다^^
혹시나 하는 마음에....해봤읍니다

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> ab = new HashMap<Integer, Integer>();
        Map<Integer, Integer> cd = new HashMap<Integer, Integer>();
        int n = A.length;
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int newVal = ab.getOrDefault(A[i] + B[j], 0) + 1;
                ab.put(A[i] + B[j], newVal);  
            }
        }
        
        for (int k = 0; k < n; k++) {
            for (int l = 0; l < n; l++) {
                result += ab.getOrDefault(-(C[k] + D[l]), 0);
            }
        }
        
        return result;
    }
}

a + b + c + d = 0
a + b = - (c + d) 를 이용하여 4중 for loop을 2중으로 바꾸기~

Runtime: 59 ms, faster than 92.03% of Java online submissions for 4Sum II.
Memory Usage: 58.6 MB, less than 45.70% of Java online submissions for 4Sum II.