[LeetCode] 3Sum

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

 

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]]

Explanation: 

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

 

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

 

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

---

 

The problem is to find all combinations of three numbers in a given array of numbers whose sum is 0.
Since Java has types, we need to be more careful when returning the result compared to JavaScript.

숫자로 이루어진 주어진 배열 내에서 3개의 숫자의 합이 0이 되는 조합을 모두 구하는 문제.

확실히 자바는 타입이 있다 보니 결과값을 리턴할 때도 자바스크립트에 비해 좀 더 신경써야 한다.

 

First, if the length of the nums array is 3,

we can simply add those three numbers, and if the sum is 0, return them as is; otherwise, return an empty array.

일단은 nums 배열의 길이가 3이면,

그냥 그 3개의 숫자를 더하고 0이면 그대로 리턴하고 아니면 빈 배열을 리턴하면 된다. 이 부분 예외 처리해 주고...

Now, considering an array of length 6 like [-1, 0, 1, 2, -1, -4]...
for the number at the i-th position,

if we pick any 2 numbers from the remaining 5 and their sum equals nums[i], that forms a valid combination.

그리고 [-1, 0, 1, 2, -1, -4] 라는 길이 6의 배열에 대해 생각해 봤을때...

i번째 자리에 있는 수에 대해, 나머지 5가지 숫자 중 2개를 뽑아서 더해서 nums[i]와 같아지면 된다.

 

If we solve it in this conceptually brute-force way, it would look something like this:

그런 개념으로 다소 비효율적으로 무식하게 풀면 아래처럼 된다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> result = new HashSet<>();
        if(nums.length == 3){
            // 1. if length of nums is 3
            int res = 0;
            for(int num:nums){
                res += num;
            }
            if(res == 0){
                result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            } else{
                return new ArrayList();
            }
        } else{
            // 2. otherwise
            for(int i=0; i<nums.length; i++){
                int sum = nums[i];
                for(int j=i+1; j<nums.length; j++){
                    for(int k=j+1; k<nums.length; k++){
                        int sum2 = nums[j] + nums[k];
                        if(sum2 + sum == 0){
                            List<Integer> sumRes = new ArrayList();
                            sumRes.add(nums[i]);
                            sumRes.add(nums[j]);
                            sumRes.add(nums[k]);
                            // delete duplicates
                            result.add(sumRes);
                        }
                    }
                }
            }
        }
        return new ArrayList<>(result);
    }
}

 

To remove duplicates, we first sort the given nums array and store potential answers in a Set to remove duplicates.

중복제거를 위해 우선 주어진 nums를 정렬해 주고, 답이 될 수 있는 목록을 Set에 우선 저장해서 중복을 제거해 줬다.

This results in a time complexity of O(n^3)!!

이렇게 하면 시간복잡도가 무려 O(n^3)이다!!

Naturally, there are three nested loops, and even if a combination is already in the result, it still gets checked again.

당연하다. 반복문이 3중으로 들어가 있고, 이미 결과에 들어가 있는 조합이어도 또 검사하게 되어 있으니.

 

 

So, of course, it results in a Time Limit Exceeded error.

그래서 당연하게도 Time Limit Exceeded가 뜬다.

At least, out of 315 test cases, 310 passed… so the logic itself is correct.

그나마 315개 테스트케이스중에 310개는 통과됐으니... 아무튼 로직 자체는 맞다는 건데.

Now, let's try to improve efficiency.

그럼 효율 개선을 더 해 보자. 

 

1. Using Two Pointers 투 포인터 사용하기

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> result = new HashSet<>();
        if(nums.length == 3){
            // 1. if length of nums is 3
            int res = 0;
            for(int num:nums){
                res += num;
            }
            if(res == 0){
                result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            } else{
                return new ArrayList();
            }
        } else{
            // 2. otherwise
            for(int i=0; i<nums.length-2; i++){
                int sum = nums[i];
                // Two pointer!
                int left = i + 1; // left end
                int right = nums.length - 1; // right end
                while(left < right){
                    int sum2 = nums[left] + nums[right];
                    if(sum + sum2 < 0){
                        left++;
                        continue;
                    } else if(sum + sum2 > 0){
                        right--;
                        continue;
                    } else if(sum + sum2 == 0){
                        List<Integer> sumRes = new ArrayList();
                        sumRes.add(nums[i]);
                        sumRes.add(nums[left]);
                        sumRes.add(nums[right]);
                        // delete duplicates
                        result.add(sumRes);
                        right--;
                        left++;
                    }
                }
            }
        }
        return new ArrayList<>(result);
    }
}

 

Using this method, it passes, but the runtime is still not very satisfying.

Using two pointers is good, but we are still relying on a Set.

I wondered if there’s a way to avoid duplicates in the result without relying on a data structure like that.

이렇게 하면 통과는 되지만, 런타임이 영 마음에 안 든다.

투 포인터를 쓰는 건 좋은데, 여전히 Set을 사용하고 있고...

이렇게 자료구조에 의존하지 않고 그냥 아예 중복값이 결과에 들어가지 않게 할 순 없을까? 하고 고민을 더 해봤다.

 

 

2. Skipping duplicate values in loops 반복문에서 중복 값 스킵하기.

Currently, every combination is checked regardless of duplicates.

현재는 중복 여부와 관계없이 모든 조합을 검사하도록 되어 있다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> result = new HashSet<>();
        if(nums.length == 3){
            // 1. if length of nums is 3
            int res = 0;
            for(int num:nums){
                res += num;
            }
            if(res == 0){
                result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            } else{
                return new ArrayList();
            }
        } else{
            // 2. otherwise
            for(int i=0; i<nums.length-2; i++){
                if(i>0 && nums[i] == nums[i-1]){
                    // if current i of num is same with i-1, skip
                    continue;
                }
                // two pointer start
                int left = i+1; // left end
                int right = nums.length-1; // right end
                while(left < right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum < 0){
                        left++;
                        continue;
                    } 
                    if(sum > 0){
                        right--;
                        continue;
                    } 
                    if(sum == 0){
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        // skip duplicate case
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return new ArrayList<>(result);
    }
}

 

We can add code to skip duplicate numbers at index i,

as well as left and right indices when using the two-pointer approach.

인덱스 i에 대해서도, left와 right에 대해서도

각각 현재 인덱스 위치의 숫자와 다음에 탐색할 위치의 숫자가 같은 경우 스킵하는 코드를 추가했다. 

While at it, I also fixed variable names that were unnecessarily named sum, sum2, etc.

하는 김에 변수명도 쓸데없이 sum, sum2 이렇게 돼있는 것들 수정하고...

With these changes, it finally passes with a satisfactory runtime!!!

그렇게 만족스러운 런타임으로 통과!!!