[Leetcode] 15. 3Sum - JS

https://leetcode.com/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
정수 배열 nums가 주어진다.
i != j, i != k, j != k이면서 nums[i] + nums[j] + nums[k] === 0
위를 만족하는 i,j,k 찾아 triplets [nums[i], nums[j], nums[k]]를 반환하라.
단, triplets는 중복된 값을 포함하지 않는다.
[-1,0,1] === [-1,1,0]이므로 [-1,0,1] 하나만 포함해야한다.

제한조건
--------------------
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5

 

2. 접근 방법

접근방법 - Two pointer
--------------------
i,j,k를 어떻게 구할지?
또 [nums[i], nums[j], nums[k]] 구성이 동일한지 어떻게 체크해서 중복된 값을 포함시킬지 말지?

오름차순 정렬한 상태에서 진행하면 어떻게 될까?
-> 오름차순 정렬하면 sum을 비교하여 포인터를 이동할 수 있다.

0. nums를 오름차순으로 정렬하고 triplets를 []로 초기화한다.
1. i 인덱스에 대한 반복문을 실행한다.
	- 이전 값과 우측 이동한 현재 값이 동일하면 pass
2. 반복문 내부에서 j,k를 각각 1, n - 1 초기화한다. 
3. j < k를 만족하면 반복한다.
    - sum < 0 이면,
        - j 우측 이동
    - sum > 0 이면
        - k 좌측 이동
    - sum === 0 이면 triplets에 추가한다.
        - j 우측 이동
        - triplets에 추가한 값과 이동한 값이 동일하면 중복값이 들어가므로
        - 이전 값과 우측 이동한 값이 동일하면 j 우측 이동 반복한다.
3. i 인덱스 반복문이 종료되면 triplets 반환

 

 

3. 코드

var threeSum = function(nums) {
    let triplets = [];
    nums.sort((a,b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        // 이전 값과 동일하면 pass
        if (nums[i] === nums[i - 1]) continue;
        
        let j = i + 1
        let k = nums.length - 1
        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k];
            if (sum < 0) {
                j++;
            } else if (sum > 0) {
                k--;
            } else {
                triplets.push([nums[i], nums[j], nums[k]])
                j++;
                /**  
                j가 이동하기 전의 값과 이동한 후 현재 값이 동일하면 
                'No duplicate' 조건에 부합하지 않으므로
                j가 이전 값과 동일하지 않은 곳까지 이동해야한다.

                만약 j가 k와 동일해지면 더 이상 triplets는 없다.
                */
                while (nums[j] === nums[j - 1] && j < k) {
                    j++;
                }
            }
        }
    }
    return triplets;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n^2)

- 공간복잡도: O(n)

 

오름차순 정렬하여 sum이 0보다 큰지 작은지에 따라 포인터를 이동시켜주는 것 까지는 접근을 제대로 했다.

투 포인터를 사용하면 중첩 반복문을 사용하지 않아야 한다는 고정관념이 있어 while문 하나에서 i, j, k 3개의 포인터를 사용했더니

조건문이 추가되면서 코드가 복잡해지고 엣지 케이스를 고려하기가 까다로워졌다.

 

다른 사람이 푼 풀이를 참고하여 j,k 투 포인터만 사용하고 i를 순회하는 중첩 반복문을 사용하고

i와 j를 이동시킬 때 이전 값과 비교하여 동일하면 pass하는 로직을 추가하여 "No Duplicate" 조건을 해결할 수 있다는 것을 배웠다.

 

Two pointer 문제를 많이 접하다보니 어느정도 패턴이 보이는 것 같아 성장한 느낌이 들어서 기분이 좋다. ㅎㅎ

비록 다른 사람 풀이를 참조해서 풀긴 했지만 한달 뒤에 다시 풀어보면 풀 수 있을 것 같다.