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:

 123 Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 

Related Topics: ArrayTwo Pointers

## 解題邏輯與實作

 12345678910111213141516171819202122232425262728293031323334 class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: assert len(nums) >= 3 , " n >= 3" diff = 2**32 ans = 0 length = len(nums) nums.sort() for first_idx, first in enumerate(nums[:-2]): if first_idx > 0 and first == nums[first_idx-1]: continue second_idx = first_idx + 1 third_idx = length -1 while(second_idx < third_idx): second = nums[second_idx] third = nums[third_idx] summation = first + second + third if abs(target-summation) < diff: diff = abs(target-summation) ans = summation if summation < target: second_idx += 1 elif summation > target: third_idx -= 1 else: break return ans 

1. 在固定首位數字後與剩餘數列中頭兩個數字，計算三數之和。若和大於 target ，則與之前紀錄下來答案相比，回傳最接近的 target 的值。
這是因為在陣列已排序且首位數字固定的情況下，剩餘數列中頭兩個數字和理應會是最小；且在尋訪的過程中，首位數字會逐漸加大，所以一旦出現首位數字與剩餘數列中頭兩個數字和大於 target 的狀況，其後的和皆會大於 target，且差值會愈來越大。因此一旦出現這狀況，即可停止尋訪。

2. 在固定首位數字後與剩餘數列中末兩個數字，計算三數之和。若和小於 target ，直接向下尋訪下一個首位數字。
這是因為在陣列已排序且首位數字固定的情況下，剩餘數列中末兩個數字之和理應是最大，因此若此值小於 target，其他和也會小於 target，且差值大於此值。因此僅需紀錄目前的狀況後，直接尋訪下一個首位數字即可，無須在考慮目前首位數字的其他組合。

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: assert len(nums) >= 3 , " n >= 3" diff = 2**32 ans = 0 length = len(nums) nums.sort() for first_idx, first in enumerate(nums[:-2]): if first_idx > 0 and first == nums[first_idx-1]: continue summation = first + nums[first_idx+1] + nums[first_idx+2] if summation > target: return summation if abs(target- summation) < diff else ans summation = first + nums[length-2] + nums[length-1] if summation < target: if abs(target- summation) < diff : diff = abs(target-summation) ans = summation continue second_idx = first_idx + 1 third_idx = length -1 while(second_idx < third_idx): second = nums[second_idx] third = nums[third_idx] summation = first + second + third if summation == target: return summation elif summation < target: second_idx += 1 else: third_idx -= 1 if abs(target-summation) < diff: diff = abs(target-summation) ans = summation return ans