[LeetCode] 454. 4Sum II

Problem

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

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1)
            for (int j : nums2)
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
        int cnt = 0;
        for (int k : nums3)
            for (int l : nums4)
                cnt += map.getOrDefault(-(k + l), 0);
        return cnt;
    }
}

Explanation

• 이 알고리즘의 핵심은 수행 시간을 줄이는 것이다. 4개의 배열에서 모든 요소들을 다 더하는 경우에는 O(N^4)의 시간 복잡도가 소요된다.
• 4개의 배열 중 2개 배열의 값을 먼저 계산하고, 나머지 2개 배열의 값을 계산한 후 비교하면 O(N^2)의 시간 복잡도가 소요된다.
• for반복문을 통해 2개 배열의 요소를 더한 후, 해당 값을 메모하기 위하 Map을 선언한다.

  Map<Integer, Integer> map = new HashMap<>();
  for (int i : nums1)
    for (int j : nums2)
        map.put(i + j, map.getOrDefault(i + j, 0) + 1);
  

• 조건을 만족하는 Tuple의 개수를 계산하기 위해 변수 cnt를 선언한다.
• 위의 2개 배열을 제외한 나머지 배열값과 Map에 저장된 값을 비교새 배열 cnt값을 증가시킨다.
• 계산된 cnt값을 반환한다.

  int cnt = 0;
  for (int k : nums3)
    for (int l : nums4)
        cnt += map.getOrDefault(-(k + l), 0);
  return cnt;