16. 3Sum Closest

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

Python

• Time: O(N^2)
• Space: O(1)

毛毛蟲式Two Pointer

from math import inf


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

        for i in range(len(nums)):
            low, high = i+1, len(nums)-1

            while low < high:
                total = nums[i] + nums[low] + nums[high]

                if abs(target-total) < abs(diff):
                    diff = target-total

                if total < target:
                    low += 1
                else:
                    high -= 1

                if diff == 0:
                    break
        return target - diff