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

短命女 2021-12-15 14:17 198阅读 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

--------------------

转载于:https://www.cnblogs.com/GoodRnne/p/10647363.html