[LeetCode] 3Sum

문제링크

3Sum - LeetCode

 

정수로 이루어진 배열 nums가 주어질 때, nums의 element 3개를 뽑아 더 한 경우 0이 되는 element들을 출력하는 문제이다.

정수 요소는 중복되어 주어질 수 있고, 중복되어 사용할 수 있다.

접근 방법

처음에는 start, mid, end 3개의 변수를 통해 nums를 순회하며 0이 되는 경우를 출력하려 하였다.

하지만 [0,0,0,0] => [0,0,0] 이 출력되어야 하는데 [[0,0,0],[0,0,0]] 처럼 중복되는 경우를 잡지 못하여서 많은 에러가 발생하여 어려움을 겪었다.

결국 검색을 통해 예외 조건을 확인하였는데 

while(start < end && nums[start] === nums[start + 1]) start++;​

while문 내에 while을 사용하여 이전 값과 다음 값이 같을때 계속해서 증감해주는 것으로 해결하였고

기존에 start, mid, end 3가지를 예외처리 하는 것에서 

start를 고정값으로 두고, mid, end를 변화하는 값으로 두는 인사이트를 얻어 더 깔끔한 코드를 짤 수 있었다.

[Leetcode / Javascript] 15. 3Sum (tistory.com)

// 숫자 배열이 주어질때 3개를 뽑아 더했을 경우 0이 되는 경우
// 그 숫자들을 배열로 넣어 출력

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let output = [];
    let fixed = 0, start = 1, end = nums.length-1;
    
    if(nums.length < 3) return output;
    
    nums.sort((a, b) => a - b);
    
    for(let fixed = 0; fixed < nums.length - 2; fixed++){
        if(nums[fixed] > 0) break;
        if(nums[fixed] === nums[fixed - 1]) continue;
        
        let start = fixed + 1, end = nums.length-1;
        
        while(start < end){
            const sum3Nums = nums[fixed] + nums[start] + nums[end];
            
            if(sum3Nums === 0) {
                output.push([nums[fixed], nums[start], nums[end]])
                while(start < end && nums[start] === nums[start + 1]) start++;
                while(start < end && nums[end] === nums[end-1]) end--;
                start++, end--;
                continue;
            }
            else if(sum3Nums < 0){
                while(start < end && nums[start] === nums[start + 1]) start++;
                start++;
            }else{
                while(start < end && nums[end] === nums[end-1]) end--;
                end--;
            }
        }
    }
    
    
    return output
};