[LeetCode] 454. 4Sum II - 문제풀이

Description

주어진 4개의 숫자 배열에서 각 요소를 더해 0이 나오는 케이스의 카운트를 반환해줍니다.

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 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

Example 2:

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

Constraints:

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

Solution 1. Hash Table

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

    Map<Integer, Integer> map = new HashMap<>(); // key: sum, value: frequency of sum.

    int n = nums1.length, result = 0;

    // Get all possible two-sums between nums3 and nums4.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int sum = nums3[i] + nums4[j];
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
    }

    // Count the number of two-sums between A and B that equals to opposite of any two-sum between nums3 and nums4.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int sum = nums1[i] + nums2[j];
            if (map.containsKey(-sum))
                result += map.get(-sum);
        }
    }

    return result;
}

우리는 가능한 모든 nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0을 찾아야하기 때문에 먼저 nums3과 nums4에서 가능한 twoSum을 sum값을 key로, count를 value로 저장합니다. 이후 nums1과 nums2에서 가능한 twoSum의 음수값과 3,4의 맵에 저장된 값이 일치할경우 0이 되므로 해당 케이스의 가능한 경우의수를 모두 더해주시면 됩니다.

Reference

4Sum II - LeetCode