【LeetCode每天一题】3Sum Closest（最接近的三数和）-蒲公英云

【LeetCode每天一题】3Sum Closest（最接近的三数和）

短命女 2021-12-15 14:17 318阅读 0赞

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)。

解决代码

1 class Solution(object): 2 def threeSumClosest(self, nums, target): 3 nums.sort() 4         min_size = 99999 # 用来记录最接近和的值的变量
 5         result = 0 # 记录最接近的三个数之和
 6         if len(nums) < 1: 7             return 0
 8         leng = len(nums) 9         for i in range(leng-2): # 第一个开始遍历 10             if i > 0 and nums[i] == nums[i-1]: # 如果相同则直接跳过。 11                 continue 
12             start,end = i+1, leng-1 # 设置首位两个指针
13             while start < end: 14                 tem =nums[i] + nums[start] + nums[end] 15                 if tem - target < 0: # 如果三数之和减去target 小于0， 然后反过来判断是否小于min_size的值， 满足的话更新result和min_size 16                     if target - tem < min_size: 17                         result = nums[i] + nums[start] + nums[end] 18                         min_size = target - tem 19                     start += 1
20                 else: # 如果三数之和减去target大于0， 然后同理进行判断 21                     if tem - target < min_size: 22                         result = nums[i] + nums[start] + nums[end] 23                         min_size = tem - target 24                     end -= 1
25         return result 26