###### tags: `Leetcode` `medium` `pointer` `python`

# 16. 3Sum Closest

## [題目連結:] https://leetcode.com/problems/3sum-closest/

## 題目:
Given an integer array ```nums``` of length ```n``` 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).

**Example 2:**

Input: nums = [0,0,0], target = 1
Output: 0

## 解題想法:
兄弟題目: [15. 3Sum](/FLggbFKASMqFH3GYi9wSsg)、[18. 4Sum](/DxMPstejSjGGRPi7EHckdA)

* 給一數組，求三數和最接近target
* 先排好數列
* for 迴圈固定i
* two pointer移動j、k
* j=i+1
* j=len(nums)
* min_val = min(min_val,abs(target-(nums[i]+nums[j]+nums[k])))

## Python:

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        min_val = float('Inf')
        ans = 0
        for i in range(len(nums)-2):
            j = i+1
            k = len(nums)-1
            while j<k:
                cur_sum = nums[i]+nums[j]+nums[k]
                if cur_sum==target:
                    return target
                #找差最少的cur_sum
                elif min_val>abs(target-cur_sum):
                    min_val = abs(target-cur_sum)
                    ans = cur_sum
                #和太小
                if target-cur_sum>0:
                    j+=1
                else:
                    k-=1
        return ans


if __name__ =='__main__':
    result = Solution()                    
    nums = [-1,2,1,-4]
    target = 1
    ans = result.threeSumClosest(nums,target)
    print(ans)