Leetcode Java 4Sum II

문제

Link

코드

class Solution {

  public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    int length = nums1.length;
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    Arrays.sort(nums3);
    Arrays.sort(nums4);
    int min = Math.min(nums1[0] + nums2[0], -(nums3[length - 1] + nums4[length - 1]));
    int max = Math.max(nums1[length - 1] + nums2[length - 1], -(nums3[0] + nums4[0]));
    int[] map = new int[max - min + 1];
    for (int num1 : nums1) {
      for (int num2 : nums2) {
        map[num1 + num2 - min]++;
      }
    }
    int result = 0;
    for (int num3 : nums3) {
      for (int num4 : nums4) {
        result += map[-num3 - num4 - min];
      }
    }
    return result;
  }

}

결과

Link

설명

1. 네 정수 배열 nums1, nums2, nums3, nums4의 요소들의 합이 0이 되는 조합의 수를 구하는 문제이다.

2. num1, num2, nums3, nums4 모두 오름차순으로 정렬한다.

3. 문제 풀이에 필요한 변수를 정의한다.
   • num1부터 nums4의 길이가 동일하므로, length에 nums1의 길이만 넣어준다.
   • min에 nums1[0]과 nums2[0]의 합과 nums3[$length - 1$]과 nums4[$length - 1$]의 합을 음수로 전환한 값 중 작은 값을 넣어준다.
   • max에 nums1[$length - 1$]과 nums2[$length - 1$]의 합과 nums3[0]과 nums4[0]의 합을 음수로 전환한 값 중 큰 값을 넣어준다.
     • min과 max는 각 배열 내 값을 이용하여 배열의 범위를 좁히기 위한 임의 변수이다.
   • 각 경우의 수를 계산하기 위한 map을 $max - min + 1$ 크기의 정수 배열로 초기화한다.
4. nums1과 nums2를 순차적으로 모든 요소들을 사용하여 반복을 수행한다.
   • 각 반복 간 map의 $num1 + num2 - min$ 위치의 값을 증가시킨다.
5. result를 0으로 초기화 하고, nums3와 nums4를 순차적으로 모든 요소들을 사용하여 반복을 수행한다.
   • 각 반복 간 result에 map의 $-num3 - num4 - min$의 값을 더해준다.
     • map의 범위를 좁히기 위해 사용된 min을 제외하고 $num1 + num2$의 값과 $-num3 - num4$의 값을 더한 값이 동일한 경우, 목표가 되는 네 값의 합이 0이 되는 경우가 되므로 result를 증가시키는 것이다.
6. 반복이 완료되면 조합의 수를 넣은 result를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.