# 16. 3Sum Closest

Medium
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
Explanation:
The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Constraints:
• `3 <= nums.length <= 500`
• `-1000 <= nums[i] <= 1000`
• `-104 <= target <= 104`

### 解題

Runtime: 20 ms, faster than 95.35%
Memory Usage: 3.2 MB, less than 85.45%
func threeSumClosest(nums []int, target int) int {
res := nums[0] + nums[1] + nums[2]
sort.Ints(nums)
for i, num := range nums {
left := i+1 //從 i+1 開始，因為 i 前面的已經跑過了
right := len(nums) - 1
for left < right {
sum := num + nums[left] + nums[right]
if abs(sum - target) < abs(res - target) {
res = sum
}
if sum == target {
return sum
} else if sum < target { // 比目標小，將 left 右移，下一次的sum會變大
left++
} else {
right-- //下一次的sum會變小
}
}
}
return res
}
func abs(a int) int {
if a < 0 { return -a }
return a
}