LeetCode 筆記 - 16. 3Sum Closest

Posted on

題目在此 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
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        length = len(nums)
        
        offset = None
        for i in range(length):
            if 0 < i and nums[i] == nums[i - 1]:
                continue
            
            left = i + 1
            right = length - 1
            while left < right:
                
                value = nums[i] + nums[left] + nums[right]
                current_offset = value - target
                if offset is None or abs(current_offset) < abs(offset):
                    offset = current_offset
                    if offset == 0:
                        break
                if value < target:
                    left += 1
                else:
                    right -= 1

            if offset == 0:
                break
                
        return target + offset

也許你也會想看看