Posted on 2022-11-17 19:29
Uriel 閱讀(57)
評論(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