Leetcode Java 3sum

문제

Link

코드

class Solution {

  public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
      if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
        int j = i + 1;
        int k = nums.length - 1;
        int sum = 0 - nums[i];
        while (j < k) {
          if (nums[j] + nums[k] == sum) {
            result.add(Arrays.asList(nums[i], nums[j], nums[k]));
            while (j < k && nums[j] == nums[j + 1]) {
              j++;
            }
            while (j < k && nums[k - 1] == nums[k]) {
              k--;
            }
            j++;
            k--;
          } else if (nums[j] + nums[k] < sum) {
            j++;
          } else {
            k--;
          }
        }
      }
    }
    return result;
  }

}

결과

Link

설명

1. 주어진 정수 배열 nums를 오름차순 정렬한다.

2. 반복문을 통해서 주어진 정수들의 합이 0이 되는 세 숫자를 탐색한다.
   • 첫 숫자 이후 두 숫자를 더 찾아야 하므로 $nums.length - 2$까지 반복을 수행한다.
   • i가 0인 경우와 i가 0초과이면서 nums[i - 1]의 값과 nums[i]의 값이 같지 않은 경우(중복되지 않은 경우)를 대상으로 탐색한다.

3. 남은 두 숫자를 탐색하기 위해 $i + 1$ 부터 다음 숫자를 탐색할 변수 j와 $nums.length - 1$부터 이전 숫자를 탐색할 변수 k를 선언하고, 세 숫자의 합을 저장할 변수 sum은 -nums[i]값으로 초기화 한다.

4. 변수 j의 값이 변수 k의 값과 크거나 같기 전까지 반복을 하여 나머지 두 숫자를 탐색한다.
   • nums[j] + nums[k]의 값이 sum과 동일하면 result 변수에 nums[i], nums[j], nums[k] 세 값을 List로 넣어주고, j와 k의 위치를 이동한다.
     • 변수 j는 변수 k의 값보다 작고, nums[j]의 값과 nums[j + 1]의 값이 같지 않을 때까지 값을 더해준다.
     • 변수 k는 변수 j보다 크거나 같고, nums[k - 1]의 값과 nums[k]의 값이 같지 않을 때까지 값을 빼준다.
   • nums[j] + nums[k]의 값이 sum보다 작으면 변수 j의 값을 더해준다.
   • 그 외의 경우는 변수 k의 값을 빼준다.
5. 반복이 완료되면 result 변수를 주어진 문제의 결과로 반환한다.

소스

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