16. 3Sum Closest (Array, Two Pointers, Sorting)

링크 - https://leetcode.com/problems/3sum-closest/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Two Pointers

우리는 가장 왼쪽 값을 기준으로 나머지 두개의 포인터를 left right로 놓아 움직이면서 target에 가까운 값을 찾아나갈 수 있다. 중요한점은 nums를 sort먼저 해줘야 이게 가능하다는 것이다.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        diff = float('inf')
        nums.sort()

        for i in range(len(nums)):
            left = i + 1
            right = len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                cur_diff = target - total
                if abs(cur_diff) < abs(diff):
                    diff = cur_diff

                if total == target:
                    return total
                elif total < target:
                    left += 1
                else:
                    right -= 1

        return target - diff

Time Complexity: O(N^2) sorting에는 nlogn이 소요되고 그 다음은 for-while때문에 N^2가 소요된다.

Space Complexity: O(logn) sorting 알고리즘에 따라 O(logn)부터 O(n)까지가 소모된다.

2) Binary Search

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        diff = float('inf')
        nums.sort()

        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                complement = target - nums[i] - nums[j]
                # right = bisect.bisect_right(nums, complement, j+1)
                right = self.bisectRight(nums, complement, j+1)
                left = right - 1

                if right < len(nums) and abs(complement - nums[right]) < abs(diff):
                    diff = complement - nums[right]
                if left > j and abs(complement - nums[left]) < abs(diff):
                    diff = complement - nums[left]
            
            if diff == 0:
                break

        return target - diff

    def bisectRight(self, arr, target, left=0, right=None):
        if right is None:
            right = len(arr)
            
        while left < right:
            mid = (left + right) // 2
            if arr[mid] > target:
                right = mid
            else:
                left = mid + 1

        return left

Time Complexity: O(N^2 * logN)

Space Complexity: O(logN) to O(N)