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:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solutions
1. Two Pointers
可以先将数组排序，然后从左到右遍历每一个数，在这个数右边使用双指针从两边往中间选两个数，看加和是否合乎要求，如果不是就按照跟目标数值的大小关系，动态调整左右指针。
# Time: O(n^2)
# Space: O(n)
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
min_gap = float('inf')
res = None
n = len(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 1
while l < r:
thd_sum = nums[i] + nums[l] + nums[r]
if thd_sum == target:
return target
elif thd_sum < target:
l += 1
else:
r -= 1
gap = abs(thd_sum - target)
if gap < min_gap:
res = thd_sum
min_gap = gap
return res
# 125/125 cases passed (96 ms)
# Your runtime beats 94.34 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)