今天是紀錄LeetCode解題的第十六天

第十六題題目：Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.

給定一個長度為n的整數數組nums和一個整數target，找出nums中的三個整數的和最接近target，回傳三個整數的和

解題思路

這題我們用跟第十五題一樣的雙指針作法，只是把判斷s=0的地方改成比較目前和target的差和close和target的差誰比較小而已，如果還不是很熟雙指針的寫法及執行過程，詳盡可以看Day15的文章

程式碼

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        close = 100000
        for i in range(len(nums)-2):
            l , r = i+1, len(nums)-1
            while l < r:       
                s = nums[i] + nums[l] + nums[r]
                if abs(s - target) < abs(close - target):
                    close = s
                elif s < target:
                    l += 1
                else:
                    r -= 1
        return close

執行過程

初始狀態

• nums = [-1,2,1,-4]
• 排序後：nums = [-4,-1,1,2]
• target = 1
• close = 100000

第一次執行(i = 0)

• l = i + 1 = 1
• r = len(nums)-1 = 3
• s = nums[0] + nums[1] + nums[3] = -4 + -1 + 2 = -3
• abs(-3 - 1) < abs(100000 - 1) → True → close = -3
• s < target → -3 < 1 → l += 1 → l = 2

• s = nums[0] + nums[2] + nums[3] = -4 + 1 + 2 = -1
• abs(-1 - 1) < abs(-3 - 1) → True → close = -1
• s < target → -1 < 1 → l += 1 → l = 3 → 跳出迴圈

第二次執行(i = 1)

• l = i + 1 = 2
• r = len(nums)-1 = 3
• s = nums[1] + nums[2] + nums[3] = -1 + 1 + 2 = 2
• abs(2 - 1) < abs(-1 - 1) → True → close = 2
• s > target → r -= 1 → r = 2 → 跳出迴圈

第三次執行(i = 2)

• l = i + 1 = 3
• r = len(nums)-1 = 3
• r = l → 跳出迴圈

最終回傳的close是第二次執行中的close = 2就是正確答案了，Day15、Day16概念類似，可以一起撰寫完成