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).
思路
这道题的思路和之前拿到三数求和的思路差不多,都是一个从头开始遍历,另外那个两个指针指向头尾。不同的一点是这里求的是三数之和最接近的选项。所以在逻辑判断处理上稍微有一些不一样。
时间复杂度为O(n2),空间复杂度为O(1)。
解决代码
class Solution(object):
def threeSumClosest(self, nums, target):
nums.sort()
min_size = 99999 # 用来记录最接近和的值的变量
result = 0 # 记录最接近的三个数之和
if len(nums) < :
return
leng = len(nums)
for i in range(leng-): # 第一个开始遍历
if i > and nums[i] == nums[i-]: # 如果相同则直接跳过。
continue
start,end = i+, leng-1 # 设置首位两个指针
while start < end:
tem =nums[i] + nums[start] + nums[end]
if tem - target < : # 如果三数之和减去target 小于0, 然后反过来判断是否小于min_size的值, 满足的话更新result和min_size
if target - tem < min_size:
result = nums[i] + nums[start] + nums[end]
min_size = target - tem
start +=
else: # 如果三数之和减去target大于0, 然后同理进行判断
if tem - target < min_size:
result = nums[i] + nums[start] + nums[end]
min_size = tem - target
end -=
return result