[leetcode 16] sum of three numbers

Thinking of this topic ： Sort + Double pointer . Less contact before , So here's a record .

If you want to achieve better time complexity , Pruning here is necessary . 

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = int(1e6)
        
        for i in range(n - 2):
            if i >= 1 and nums[i] == nums[i-1]:
                continue
            
            left, right = i + 1, n - 1

            #####################  Pruning optimization  ####################
            if nums[i] + nums[left] + nums[left+1] > target:
                right = left + 1
            if nums[i] + nums[right-1] + nums[right] < target:
                left = right - 1
            ###################################################

            while left < right:
                sums = nums[i] + nums[left] + nums[right]
                
                if abs(best - target) > abs(sums - target):
                    best = sums

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

        return best