3sum, Leetcode medium - java

문제

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
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: []

나의 풀이

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();
        Set<Integer> threeSum = new HashSet<>();
        
        Arrays.sort(nums);
        
        if(nums.length < 3) {
            return new ArrayList<>();
        }
        
        for(int i=0; i<nums.length; i++) {
            int result = -nums[i];
            threeSum.clear();
            for(int j=i+1; j<nums.length; j++) {
                if(threeSum.contains(result - nums[j])) {
                    set.add(Arrays.asList(nums[i], nums[j], (result - nums[j])));
                }
                threeSum.add(nums[j]);
            }
        }
        return new ArrayList<>(set);
    } 
}

• a+b+c = 0 이 되는 숫자를 찾는 것이므로, a+b = -c 라고 생각하여 풀이하였다.
  이 과정에 HashSet을 두번 사용하였다. 첫번째 threeSum HashSet은 값을 넣기 위한 용도라, 굳히 HashSet을 사용할 필요는 없었다...
  두번째는 [a,b,c] 배열이 중복되면 안되므로, 중복을 허용하지 않는 HashSet을 활용하였다.
  이와 같이 풀으니1083 ms 라는 매우 느린 속도가 나왔다...
  그래서 다른 사람들의 풀이를 참고하여 다시 풀어보았다.

다른 풀이

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 오름차순 정렬
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i=0; i< nums.length; i++) {
            // 첫번째 원소가 양수이면, nums 배열이 양수만 존재하므로 return
            if(nums[i] > 0) {
                return result;
            }      
            // 중복 제거
            if(i>0 && nums[i] == nums[i-1]) {
                continue;    
            }
            int left = i+1;
            int right = nums.length-1;

            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if(sum > 0) {
                    right--;
                }
                else if(sum < 0) {
                    left++;
                }
                else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    // 중복 제거
                    while(left<right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while(left<right && nums[right] == nums[right+1]) {
                        right--;
                    }   
                }   
            }  
        }
        return result;
    }
}

• 위 풀이는 중복 제거를 위해 HashSet을 사용하지 않고, 조건문에 의해 중복을 걸러내는 방식이다.

• 위 그림과 같이 nums[i]와 nums[left], nums[right]의 합이 0 보다 크면 right를 감소하고,
  0보다 작으면 left를 증가시킨다.
  그리고 합이 0 이 되면, 리스트에 해당 배열을 넣고, left와 right을 둘 다 각각 뒤와 앞 인덱스로 이동시킨다.
  하지만 이동 시킨 left와 right이 전 인덱스 값과 같다면 left의 경우는 한칸 더 뒤로, right의 경우는 한칸 더 앞으로 이동한다.
  왜냐하면 값이 같다면, 세개의 수가 합쳐서 0의 되는 숫자들이 같을 수 밖에 없기 때문이다.
  위 과정을 주어진 nums 배열의 길이만큼 반복한다.

• 위와 같은 방법으로 해결하니 실행속도가 17 ms 가 나왔다.
  아무래도 HashSet을 사용하는 방식이 반복문의 로직을 더 많이 실행하여 이와 같은 속도차이가 나게된 것 같다.

Link

https://leetcode.com/problems/3sum