[Reet code] 16. 3Sum Closest

Intuition

한 점을 고정한 후 투포인터로 풀 수 있다. 이전에 푼 문제와 동일하다.

Approach

방법은 간단하다. 한점을 고정한 후에 좌, 우 바운더리를 줄여가면서 최상의 값을 찾는다. 둘중에 타겟과 더 가까운 값을 찾아, 이를 저장한다.

Complexity

• Time complexity: O(NlogN)
  sort 를 해서 O(NlogN) 의 시간복잡도를 가진다. 반복문 안에 반복문이 있긴 하지만 정렬과 동일하거나 더 작은 복잡도를 가진다.

• Space complexity: O(1)

Code

const getMoreCloseNum = (target: number, compare1: number, compare2: number) => {
    const dis1 = target - compare1 > 0 ? target - compare1 : compare1 - target
    const dist2 = target - compare2 > 0 ? target - compare2 : compare2 - target

    return dis1 < dist2 ? compare1 : compare2
}

function threeSumClosest(nums: number[], target: number): number {
    const sortedNums = nums.sort((a, b) => a - b)
    let result = 10000000
    for (let i = 0; i < sortedNums.length - 2; i++) {
        let left = i + 1
        let right = sortedNums.length - 1
        let temp
        while (left < right) {
            temp = sortedNums[i] + sortedNums[left] + sortedNums[right]
            if (temp < target) {
                left++
            } else if (temp > target) {
                right--
            } else {
                return target
            }
            result = getMoreCloseNum(target, temp, result)
        }
    }
    return result
    
};