题目: 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案
离谱
我的双指针时间复杂度，应该是O(n2)呀，总是时间超出限制，与小伙伴帮我看看不~
class Solution:
def threeSumClosest(self, nums: list[int], target: int) -> int:
nums.sort()
n = len(nums)
flag = abs(nums[0] + nums[1] + nums[n-1] - target) # flag的初始值，flag用来衡量与target之间的距离
sum = nums[0] + nums[1] + nums[n-1] # sum的初始值
#初始时：a, b, c = 0, 1, n-1
for a in range(n):
if nums[a] == nums[a-1]: #小优化，找下一个不同的值
continue
for b in range(a+1,n): #b从a的右边开始找
for c in range(n-1,b,-1): #c从最右边开始逆序寻找
if c <= b or b <= a:
break
else:
flag = min(abs(flag), abs(nums[a] + nums[b] + nums[c] - target))
if flag == abs(nums[a] + nums[b] + nums[c] - target):
sum = nums[a] + nums[b] + nums[c]
if nums[a] + nums[b] + nums[c] - target == 0: #最接近target的sum就是差距为0
sum = target
return sum
elif nums[a] + nums[b] + nums[c] - target > 0:
c -= 1
if nums[c] == nums[c + 1]:
continue
else:
b += 1
if nums[b] == nums[b - 1]:
continue
return sum
if __name__ == '__main__':
nums = [1,1,1,0]
target = 100
print(Solution.threeSumClosest(Solution,nums,target))
看到一个老哥的解法，我觉得很不错，分享一下
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums = sorted(nums)
res = sum(nums[0:3])
for i in range(len(nums)-1):
l, r = i+1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total < target:
l += 1
elif total > target:
r -= 1
elif total == target:
return total
if abs(res-target) > abs(total-target):
res = total
return res
