我是靠谱客的博主 现代银耳汤,最近开发中收集的这篇文章主要介绍16 -最接近的三数之和 - python,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

这道题和15 - 三数之和 - python区别并不大,所以可以重用大部分的代码。分析题意,题目要求在数组中找到三个数使其之和最接近与target,并且答案唯一,那么:

  • 当数组元素个数小于3时,直接返回None,表示答案不存在
  • 当数组元素个数等于3时,直接返回数组之和
  • 当数组元素个数大于3时,需要设置minDiff记录当前三数之和和target的差距,同样设置leftright两个指针,然后重复以下判断过程,直到left >= right:
    • 如果nums[cur] + nums[left] + nums[right] == target,直接返回三数之和,由于答案唯一,所以这里不需要再移动leftright判断其他的情况
    • 如果 nums[cur] + nums[left] + nums[right] != target,则计算与target的差距,如果它的绝对值小于minDIff,则需要更新minDiff,然后同样根据情况更新leftright
      • 如果当前三数之和小于target,则left右移,
      • 如果当前三数之和大于target,则right左移
      • 同样为了避免不必要的判断,这里需要判断当前leftright所指元素和它上一个元素是否相同

AC code

import sys
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3: return None
        if len(nums) == 3: return sum(nums)
            
        minDiff = sys.maxsize
        nums.sort()
        for cur in range(len(nums)-2):
            if cur > 1 and nums[cur] == nums[cur - 1]:
                continue
            left = cur + 1
            right = len(nums) - 1
            while left < right :
                threeSum = nums[cur] + nums[left] + nums[right]
                diff = threeSum - target
                if diff == 0:
                    return threeSum
                elif abs(diff) < minDiff:
                    minDiff = abs(diff)
                    closestSum = threeSum

                if diff < 0:
                    left += 1
                    while left < right and nums[left]==nums[left - 1]:
                        left +=1
                else:
                    right -= 1
                    while left < right and nums[right]==nums[right + 1]:
                        right -= 1
        return closestSum


最后

以上就是现代银耳汤为你收集整理的16 -最接近的三数之和 - python的全部内容,希望文章能够帮你解决16 -最接近的三数之和 - python所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(60)

评论列表共有 0 条评论

立即
投稿
返回
顶部