[LeetCode] 15. 3Sum - 문제풀이

Description

주어진 배열에서 서로 다른 요소의 합이 0이 되는 모든 순열을 반환하는 문제입니다.

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^5 <= nums[i] <= 10^5

Solution 1. Two Pointer + Set

public List<List<Integer>> threeSum(int[] nums) {

    Set<List<Integer>> result = new HashSet<>();  // 정렬이 되어있기에 순서가 다르지 않다.
    if(nums == null || nums.length < 3){return new ArrayList<>(result);}

    Arrays.sort(nums);
    for (int i = 0; i < nums.length-2; i++) {

       int j = i+1;
       int k = nums.length-1;
       while (j<k){
           int sum = nums[i]+nums[j]+nums[k];
           if(sum == 0){
               result.add(Arrays.asList(nums[i],nums[j++],nums[k--]));
           }else if(sum < 0){ // 값을 올려야하니 왼쪽 포인터 이동
               j++;
           }else if(sum > 0) { // 값을 내려야하니 오른쪽 포인터 이동
               k--;
           }
       }
    }
    return new ArrayList<>(result);
}

정렬 후 첫번째 숫자 기준으로 반복하며 남은 숫자의 범위에서 이진트리로 sum이 0이 되는 케이스를 결과에 넣습니다. Set 자료구조를 이용해 중복되는 값을 제거 후 List를 반환합니다.

Reference

3Sum - LeetCode