Posted on 2022-11-17 19:29
Uriel 阅读(24)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
游标.移动窗口
给一堆数字，第15题是要输出加和正好等于目标数值的所有三个数的三元组，本题是要输出最接近目标数值的三个数之和，默认只有一个答案，用了和第15题类似的思路
先sort list，枚举第一个数i=1~n-2，然后设置两个游标，左边从i+1向右，右边从n向左，更新如果三个数之和于目标值差距，如果三数之和小于目标值，第一个游标右移，否则第二个右边左移Runtime: 1781 ms, faster than 78.79% of Python online submissions for 3Sum Closest.
Memory Usage: 13.5 MB, less than 52.25% of Python online submissions for 3Sum Closest.
1 #16
2
3 class Solution(object):
4 def threeSumClosest(self, nums, target):
5 """
6 :type nums: List[int]
7 :type target: int
8 :rtype: int
9 """
10 nums.sort()
11 min_diff = 60001
12 for i in range(len(nums)):
13 pos1 = i + 1
14 pos2 = len(nums) - 1
15 while pos1 < pos2:
16 t_sum = nums[pos1] + nums[pos2] + nums[i]
17 if abs(target - t_sum) < min_diff:
18 min_diff = min(min_diff, abs(target - t_sum))
19 ans = t_sum
20 if abs(target - t_sum) == 0:
21 return target
22 if target > t_sum:
23 pos1 += 1
24 else:
25 pos2 -= 1
26 return ans