16. 最接近的三数之和(threeSumClosest)

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1

输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1

输出：0

提示：

3 <= nums.length <= 1000

-1000 <= nums[i] <= 1000

-104 <= target <= 104

来源：力扣（LeetCode）

链接：/problems/3sum-closest

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解1：

执行用时：996 ms, 在所有 Python3 提交中击败了17.65%的用户

内存消耗：16.2 MB, 在所有 Python3 提交中击败了15.52%的用户

通过测试用例：99 / 99

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        res = None
        nums.sort()
        nums_len = len(nums)
        ovi = None
        for i in range(0, nums_len - 2):
            vi = nums[i]
            if vi == ovi:
                continue
            ovi = vi
            j = i + 1
            k = nums_len - 1
            ovj = None
            ovk = None
            vs = None
            while j < k:
                vj = nums[j]
                if vj == ovj:
                    j = j + 1
                    continue
                vk = nums[k]
                if vk == ovk:
                    k = k - 1
                    continue
                    
                temp_vs = vi + vj + vk
                if vs is None:
                    vs = temp_vs
                else:
                    if abs(temp_vs - target) < abs(vs - target):
                        vs = temp_vs

                if temp_vs < target:
                    j = j + 1
                    ovj = vj
                elif temp_vs > target:
                    k = k - 1
                    ovk = vk
                else:
                    return target

            if res is None:
                res = vs
            else:
                abs_res = abs(res - target)
                abs_vs = abs(vs - target)
                if abs_vs < abs_res:
                    res = vs

        return res