[leetcode #15] 3Sum

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

・ 0 <= nums.length <= 3000
・ -10⁵ <= nums[i] <= 10⁵

Idea

3Sum 문제는 leetcode에서 3Sum Closet라는 문제로 등장한 적이 있었다. 그 때도 어떻게 풀어야 될지 헤메다 결국 못 풀었는데, 오늘도 똑같았다. 구글에서 검색하니 뱀귤 블로그에 좋은 풀이가 있어서 해당 풀이를 참고해서 문제를 풀었다.

문제를 보면 duplicate triplet을 포함하면 안 된다는 제약사항이 있다. 그래서 array를 탐색할 때 똑같은 원소인 경우 다음 원소로 넘어가는 것이 중요하다.

합을 구할 때 우선 array를 정렬해야 한다. 정렬해야 하는 이유는 앞뒤로 index를 조정해가며 합을 구하기 유리하기 때문이다.

정렬이 끝난 뒤 array의 모든 원소를 탐색한다. 기준이 되는 원소를 처음부터 nums.length-2까지로 정한다. 기준이 되는 원소를 정한 뒤, 해당 원소보다 뒤에 있는 원소들 중 합이 0이 되는 원소들을 찾는다.

우선 기준의 바로 뒤를 left index로 전체 array의 마지막 index를 right index로 정한다. 이후 left와 right, 그리고 기준 원소의 합이 0이 되는지 확인한다.

만약 합이 0이면 원소들을 list로 만들어 res array에 더한다. 그리고 left와 right index를 답으로 채택한 원소와 다를 때까지 각각 왼쪽과 오른쪽으로 이동시킨다.

합이 0보다 크면 right index를 감소시킨다.

합이 0보다 작으면 left index를 증가시킨다.

위와 같은 과정을 반복하면 기준으로 잡은 원소와 left, right인 원소들의 합이 0이 되는 조합을 찾을 수 있다.

이후엔 기준을 오른쪽으로 이동시키면서 0이 되는 조합을 전부 찾는다.

Solution

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

Reference

https://leetcode.com/problems/3sum/
https://bcp0109.tistory.com/124