題目出處

• 533 · Two Sum – Closest to target
• Google | Onsite | Two Sum – Closest to Target

難度

medium

個人範例程式碼 – two pointers

from typing import (
    List,
)

class Solution:
    """
    @param nums: an integer array
    @param target: An integer
    @return: the difference between the sum and the target
    """
    def two_sum_closest(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1

        ans = float("inf") # biggest value

        nums.sort()
        start, end = 0, len(nums) - 1
        while(start < end):
            print(ans)
            if target - (nums[start] + nums[end]) == 0:
                return 0 # early return
            elif target > (nums[start] + nums[end]): # sum is smaller than target
                ans = min(ans, target - (nums[start] + nums[end]))
                start += 1
            else: # target < (nums[start] + nums[end]) # sum is bigger than target
                ans = min(ans, (nums[start] + nums[end]) - target)
                end -= 1
        else:
            return ans

算法說明

先 sort 後以 two pointers 處理，這邊容易有個思考上的盲點，
就是如果「減去負數」的處理不就「數值會變更大」了嗎?

• 這部分可以看下圖：

我們會發現其實 target 的移動與結果影響不大。
就算是”減去””負的”，也只是「往離 target」更遠的方向前進。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

處理 input 為 [] 的情況，輸出 -1。 (題目沒說，但做為表示找不到結果)

Boundary conditions

結束條件

相向相交時，start < end

Reference

• 两数和的最接近值 · Two Sum – Closest to target