专业做制作网站信息发布推广方法
【LeetCode】打卡–Python3算法16. 最接近的三数之和
题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
结果
执行用时 : 156 ms, 在3Sum Closest的Python3提交中击败了60.60% 的用户
内存消耗 : 13.2 MB, 在3Sum Closest的Python3提交中击败了24.37% 的用户
Python解答
如果使用暴力法，三重循环的话，会显示时间复杂度太高，不通过。
于是选择使用外层循环，加上里层双向指针，时间复杂度为O(N*N)
import math
class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()data = math.infsumClosest = 0for i in range(len(nums)-2):j = i + 1k = len(nums) - 1while(j<k):delta = nums[i] + nums[j] + nums[k] - targetif(delta==0):return targetelif(abs(delta)>=data and delta>0):k = k - 1continueelif(abs(delta)>=data and delta<0):j = j + 1continueelif(abs(delta)<data and delta>0):data = abs(delta)sumClosest = nums[i] + nums[j] + nums[k]k = k - 1else:#(abs(delta)<data and delta<0)data = abs(delta)sumClosest = nums[i] + nums[j] + nums[k]j = j + 1return sumClosest
我们下次再见，如果还有下次的话！！！
欢迎关注微信公众号：516数据工作室
