Saved from https://leetcode.com/problems/3sum-closest/

lc16

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        """
        One outer loop + Two pointer
        Time: O(n^2)
        Space: O(1)
        """
        nums.sort()
        n = len(nums)
        closest_distance = float('inf') 
        closest_sum = 0
        for start in range(n-2):
            l, r = start + 1, n - 1
            while l < r:
                curr_sum = nums[start] + nums[l] + nums[r]
                if curr_sum > target:
                    r -= 1
                elif curr_sum < target:
                    l += 1
                else:
                    return target
                if abs(curr_sum - target) < closest_distance:
                    closest_distance = abs(curr_sum - target)
                    closest_sum = curr_sum
        return closest_sum
        
    def binary_search_solution(self, nums: List[int], target: int) -> int:
        """
        Enumeration + Binary search
        1) Sort nums
        2) Enumerate all the subarrays, find the closest idx within each subarray
        3) The global closest triplet is the answer
        
        Time: O(n^2 * log(n))
        Space: O(1)
        """
        nums.sort()
        n = len(nums)
        closest_distance = float('inf') 
        closest_sum = 0
        l, r = 0, n - 1
        for l in range(n-2):
            for r in range(l+2, n):
                (distance, idx) = self.search(l + 1, r - 1, target - nums[l] - nums[r], nums)
                if distance == 0:
                    return target
                curr_sum = nums[l] + nums[r] + nums[idx]
                if distance < closest_distance:
                    closest_distance = distance
                    closest_sum = curr_sum
        return closest_sum

    def search(self, lo: int, hi: int, target: int, nums: List[int]) -> (int, int):  # return (abs diff, high)
        while lo + 1 < hi:
            mid = floor((lo + hi) / 2)
            if nums[mid] == target:
                return (0, mid)
            elif nums[mid] < target:
                lo = mid
            else:
                hi = mid
        
        lo_diff = abs(nums[lo] - target)
        hi_diff = abs(nums[hi] - target)
        return (lo_diff, lo) if lo_diff < hi_diff  else (hi_diff, hi)