【游戏开发】【leetocode】16.最接近的五打一之和

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

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

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

class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# 最垃圾的方法
# 遍历一遍，取结果
# ret = nums[0]+nums[1]+nums[2]
# # print(ret)
# for i1 in range(len(nums)):
#     for i2 in range(i1+1,len(nums)):
#         for i3 in range(i2+1,len(nums)):
#             temp = 0
#             temp = nums[i1]+nums[i2]+nums[i3]
#             if temp == target:
#                 return temp
#             # print(temp)
#             if abs(ret-target)>abs(temp-target):
#                 ret = temp
#             else:
#                 ret = ret
# return ret
# v2.0 上左右指针 减少遍历
# nums.sort()  # 使左边最小 右边最大 方便判断
# ret = nums[0]+nums[1]+nums[2]
# for i in range(len(nums)):
#     l = i+1  # 左指针
#     r = len(nums)-1  # 右指针
#     while l<r:
#         temp = 0
#         temp = nums[i]+nums[l]+nums[r]
#         if temp == target:
#             return temp
#         if abs(ret-target)>abs(temp-target):
#             ret = temp
#         elif target < temp:
#             r -= 1
#         else:
#             l += 1
# return ret
# v3.0 算法依旧是左右指针
# 改进之处在于 diff = abs(target - ret), 用变量接一下abs(), 减少了abs()每次调用需要的计算时间
if len(nums) < 3:
return []
nums.sort()
ret = nums[0] + nums[1] + nums[2]
diff = abs(target - ret)
for i in range(len(nums)-2):
l, r = i+1, len(nums)-1
while l < r:
temp = nums[i] + nums[l] + nums[r]
if abs(target - temp) < diff:
ret = temp
diff = abs(target - temp)
if temp == target:
return temp
elif temp < target:
l = l + 1
else:
r = r - 1
return ret
# 自己重写abs() 也会提高一点速度
# 肯定有更快的算法，作者垃圾 不会