Description:
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

思路
第一個直覺是排序
因此 把nums進行排序
再來就是 怎麽設 close 值: 離 target 最近的那個
兩層 迴圈 排出組合
第一層 可以想成跑 每一個數 和其他兩個數的各種可能
第二層 套用 左右指針概念 假如三數目前 超過 target --> 右指針往左
假如三數目前 小於 target --> 左指針往右
等於的話 Very Good 直接回傳答案

Note: 每一個數 不行和 left 和 right 重複到 並且 第一層 每跑一個數,記得 reset left 和 right 值

正解

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 排序  
        nums.sort()
        print(nums)
        left = 0 
        right = len(nums)-1
        ans = 0 
        if len(nums) ==3:
            return nums[0]+nums[1]+nums[2]
        close = 10000 
        for i in range(len(nums)):
            right = len(nums)-1
            left = i+1
            if i == left or i == right : 
                continue            
            while left < right:
                if (nums[left]+nums[right]+nums[i]) < target:
                    print("<")
                    print(i,left,right)
                    if abs(target-(nums[left]+nums[right]+nums[i])) < close:
                        close = abs(target-(nums[left]+nums[right]+nums[i]))
                        ans = nums[left]+nums[right]+nums[i]
                    left += 1
                elif (nums[left]+nums[right]+nums[i]) > target:
                    print(">")   
                    print(i,left,right)
                    if abs(target-(nums[left]+nums[right]+nums[i])) < close:
                        close = abs(target-(nums[left]+nums[right]+nums[i]))
                        ans = nums[left]+nums[right]+nums[i]
                    right -= 1
                else:
                    print("=")
                    print(i,left,right)
                    print("equal")
                    return (nums[left]+nums[right]+nums[i])
        return ans