【leetcode 16】三数之和

本题思路：排序 + 双指针。之前较少接触，因此在此记录一下。

若想达到比较好的时间复杂度，这里的剪枝是必需的。 

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

            ##################### 剪枝优化 ####################
            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