[LeetCode 15] 3Sum (Java)

https://leetcode.com/problems/3sum/description/?page=1&search=332

---

풀이

이 문제는 정수 배열 nums가 주어졌을 때, 세 수의 합이 0이 되는 묶음을 모두 반환하는 문제이다.

먼저, 브루트포스로 풀이할 생각을 할 수 있을 것이다. 하지만, $3 \le N \le 3000$이므로 $O(N^3)$은 시간초과가 발생할 수 밖에 없다.

1. 투포인터

다음 풀이로는 투포인터를 변형한 방식이 있다.

먼저, i로 정렬된 배열 중 하나를 가리키게 한 뒤, j가 i + 1을 가리키게 하고 k로 마지막 원소를 가리키게 한다.

이후, 세 수의 합 nums[i] + nums[j] + nums[k]이 0보다 작다면, j를 오른쪽으로 이동시켜, 세 수의 합을 증가시킬 수 있다.

만약 세 수의 합이 0보다 크다면, k를 왼쪽으로 이동시켜 세 수의 합을 감소시킬 수 있다.

그리고 세 수의 합이 0이 된다면, [nums[i], nums[j], nums[k]]를 저장해주고 j나 k를 이동시킨다.

Set을 이용한 풀이

하지만, 리턴 값에 중복된 묶음이 포함되면 안되기 때문에 간편하게는 Set을 이용할 수 있을 것다.

코드로 구현해보면 다음과 같다.

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

Set을 이용하지 않는 풀이

이제 Set을 사용하지 않는다면, 일일이 중복을 제거해야한다. 즉, i, j, k 각각 같은 수를 가리키지 않도록 처리해야한다.

i는 nums[i] == nums[i - 1]를 만족한다면, continue를 하도록 하면 된다.
j는 nums[j] == nums[j + 1]를 만족하지 않을 때까지, j++을 반복해주면 된다.
k는 nums[k] == nums[k - 1]를 만족하지 않을 때까지, k--를 반복해주면 된다.

이를 코드로 구현해보면 다음과 같다.

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