LeetCode (454) - 4Sum II

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- 4Sum II

• Acceptance: 56.4%
• Difficulty: Medium

문제 설명

길이가 n으로 같은 Integer배열 nums1, nums2, nums3, nums4 가 주어진다. 해당 배열마다 하나의 원소를 꺼내어 합이 0이 되는 경우의 수를 구해라.

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

예시 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

예시 2

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

문제 풀이

• n이 최대 200 이므로 O(N^4)로는 시간초과

• nums1과 nums2의 합 sum1, nums3과 nums4의 합 sum2를 이용해 0이 되는 경우의 수를 조사하는 방식으로 접근
  - sum1과 sum2의 길이는 각각 n^2 이 되고 결국 탐색의 수는 n^2 * n^2 이므로 n^4로 똑같음.

• sum1과 sum2를 list가 아닌 Map으로 만들어 중복되는 연산을 줄인다. Key: 두 수의 합, Value: 중복 수. 두 개의 Map을 탐색하며 Key의 합이 0인 경우 Value의 곱연산을 result에 추가. -> 방법1

• 다른 사람의 풀이 참조 후 Map을 하나만 생성 후 하나의 Map을 탐색하는 방식으로 시간을 매우 줄일 수 있었음 -> 방법2

• 둘의 속도 차이는 많이 남. 방법1: 1500ms, 방법2: 150ms

코드

import java.util.HashMap;
import java.util.Map;

class Solution {
    /* 방법1 */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result = 0, n = nums1.length;
        Map<Integer, Integer> sMap1 = new HashMap<>(), sMap2 = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum1 = nums1[i] + nums2[j];
                int sum2 = nums3[i] + nums4[j];

                sMap1.put(sum1, sMap1.getOrDefault(sum1, 0) + 1);
                sMap2.put(sum2, sMap2.getOrDefault(sum2, 0) + 1);
            }
        }

        for (Map.Entry<Integer, Integer> entry1 : sMap1.entrySet()) {
            for (Map.Entry<Integer, Integer> entry2 : sMap2.entrySet()) {
                if (entry1.getKey() + entry2.getKey() == 0) {
                    result += entry1.getValue() * entry2.getValue();
                }
            }
        }

        return result;
    }

    /* 방법2 */
    public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result = 0, n = nums1.length;
        Map<Integer, Integer> sMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = nums1[i] + nums2[j];

                sMap.put(sum, sMap.getOrDefault(sum, 0) + 1);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = nums3[i] + nums4[j];

                result += sMap.getOrDefault(-sum, 0);
            }
        }

        return result;
    }
}