題目在此 16. 3Sum Closest
給一個數列跟 target,請找出相加最接近 target 的三個數
解題思維
如果沒解過 15. 3Sum,可以先解這題
這題需要使用 Two Pointers 大法
而跟 15. 3Sum 不一樣的地方是,這裡需要紀錄最相近的差
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: if (size := len(nums)) == 3: return sum(nums)
nums.sort()
result = 0 offset = inf
for i in range(size - 2): if i != 0 and nums[i - 1] == nums[i]: continue
target_0 = nums[i]
left = i + 1 right = size - 1
while left < right: target_1 = nums[left] target_2 = nums[right]
cur_t = target_0 + target_1 + target_2
if cur_t == target: return target
cur_offset = abs(cur_t - target) if cur_offset < offset: offset = cur_offset result = cur_t if cur_t < target: left += 1 else: right -= 1
return result
|
也許你也會想看看