Leetcode - 3SUM(자바스크립트 포함)

오늘은 3합 알고리즘 문제를 푸는 방법을 보여드리겠습니다.

문제는 다음과 같습니다.


이전 블로그에서 2Sum 알고리즘에 대한 솔루션에 대해 이야기했습니다. 이 문제를 위해. 2Sum 알고리즘의 솔루션과 유사하게 해시 테이블을 사용하여 모든 숫자를 저장할 수 있었습니다. 그런 다음 이중 "for"루프를 수행하고 현재 숫자의 보수가 테이블에 이미 존재하는지 확인할 수 있습니다. 그러나 그것은 이 문제를 해결하는 가장 효율적인 방법이 아닙니다.

대신 O(n^2) 시간 복잡도를 제공하는 두 개의 포인터를 사용하여 이 문제를 해결할 것입니다. 이 접근 방식에서 가장 먼저 해야 할 일은 주어진 배열을 오름차순으로 정렬하는 것입니다.

배열을 정렬한 후 배열을 반복하고 두 개의 포인터를 설정합니다. 왼쪽 포인터는 현재 숫자 바로 뒤에 오는 숫자로 설정되고 오른쪽 포인터는 배열 끝에 있는 숫자로 설정됩니다. 그런 다음 현재 숫자, 왼쪽 숫자 및 오른쪽 숫자의 합인 현재 합계를 찾을 것입니다.

이제 현재 합계가 목표 합계(이 경우 0)와 같은지 확인합니다.

같으면 최종 배열(triplet)에 세 개의 숫자를 추가하기만 하면 됩니다.

현재 합계가 0보다 작으면 왼쪽 포인터를 오른쪽으로 1씩 이동하여 합계를 늘립니다. 이전에 주어진 배열을 오름차순으로 정렬했기 때문에 각 숫자가 왼쪽에 있는 숫자보다 크다는 것을 알고 있습니다.

현재 합계가 0보다 크면 각 숫자가 오른쪽에 있는 숫자보다 작다는 것을 알고 있으므로 오른쪽 포인터를 왼쪽으로 1씩 이동하여 합계를 줄일 수 있습니다.

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

    for(let i=0; i < array.length - 2; i++){
        if(array[i] != array[i-1]){ // making sure our solution set does not contain duplicate triplets
            let left = i + 1;
          let right = array.length - 1;

            while (left < right){
                const currentSum = array[i] + array[left] + array[right];
                if (currentSum === 0){
                    triplets.push([array[i], array[left], array[right]]);
                    while(array[left] == array[left + 1]) left ++
                    while(array[right] == array[right - 1]) right -- // making sure our solution set does not contain duplicate triplets
                    left ++;
                    right --;
                } else if(currentSum < 0) {
                    left ++
                } else if(currentSum > 0){
                    right --
                }
            }
        }
    }
    return triplets
};