3Sum

---

💬 문제

[문제 링크]

정수 배열 nums
세개의 요소 합이 0이 되는 값들을 찾아
각 경우의 수를 배열로 반환
배열과 배열 내의 숫자 순서는 상관 없지만
똑같은 값을 가지는 것은 불가능

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

✍️ 나의 풀이

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let res = [];

    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 2; i++) {
        if (i !== 0 && 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)
                k--;
            else if (sum < 0)
                j++;
            else {
                res.push([nums[i], nums[j], nums[k]]);
                j++;
                while (nums[j] === nums[j - 1])
                    j++;
            }
        }
    }
    
    return res;
};

우선 주어진 배열을 오름차순으로 정렬
앞에서부터 순회하면서 하나의 인덱스를 기준으로 잡고
나머지 두개를 TwoSum 때처럼 왼쪽, 오른쪽으로 나누어 구하기
0이 되면 배열에 세 값을 배열로 push
중복을 넣지 않기 위해서 i값이나 j값이 이전과 같으면 넘어가기

📌 결과

Accepted
Runtime 158ms (Beats 66.23%)
Memory 64.29MB (Beats 90.82%)

📚 러닝 포인트

세 개의 합은 어떻게 구하지? 고민하던 차에 힌트에 하나를 기준으로 잡아두면 나머지 둘의 합만 구하면 된다! 라는 문장을 보고 바로 Two Sum을 떠올려 적용시켰다. 그리고 나서는 중복을 제거하는게 문제였는데, 1차적으로 i가 같을 때 순회하지 않고 넘기는 것은 바로 떠올랐다. 기준이 같은 값이면 나머지 둘의 값도 똑같을 테니까. 하지만 합이 0이 되었을 때 즉, 나머지 둘의 값이 인덱스는 다르나 같은 숫자일 때가 문제였다. 그러다가 이것도 똑같이 둘 중 한쪽이 다른 숫자일 때까지 이동하면 된다는 것을 알았다. sorting을 해둔 것의 이점이었다. for문 안에 while문 안에 while문이라니 조금 싫었지만 어쨌든 해내었다. 그리고 sort를 사용하면서 다시 깨달은 게 있는데, javascript의 array.sort()는 숫자도 문자열로 변환한 다음에 정렬하기 때문에 [1, 2, 100]이 아닌 [1, 100, 2]로 정렬된다. 따라서 숫자를 가지고 정렬하고 싶을 때는 오름차순이든, 내림차순이든 비교 함수를 꼭꼭 작성해주자.