""" No. 016 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。 找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 [例如]，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). """
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n <= 3:
            return sum(nums)
        nums.sort()
        ans = nums[0] + nums[1] + nums[2]
        for i in range(n):
            L = i + 1
            R = n - 1
            while(L < R):
                csum = nums[i] + nums[L] + nums[R]
                if abs(csum - target) < abs(ans - target):
                    ans = csum
                if csum > target:
                    R = R - 1
                elif csum < target:
                    L = L + 1
                elif csum == target:
                    return ans
        return ans