題目出處

16. 3Sum Closest

難度

medium

個人範例程式碼

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if not nums or len(nums) < 3:
            return -1

        nums.sort()
        ans = float("inf")

        for idx, first_num in enumerate(nums):
            ans = self.two_sum(nums, target, ans, first_num, idx+1, len(nums)-1)    

        return ans

    def two_sum(self, nums, target, ans, first_num, left, right):
        while(left < right):
            if first_num + nums[left] + nums[right] == target:
                return target
            elif first_num + nums[left] + nums[right] < target:
                ans = self.find_closest(ans, first_num + nums[left] + nums[right], target)
                left += 1
            else: # if first_num + nums[left] + nums[right] > target:
                ans = self.find_closest(ans, first_num + nums[left] + nums[right], target)
                right -= 1
        else:
            return ans      

    def find_closest(self, a, b, target):
        if abs(a - target) <= abs(b - target):
            return a
        else:
            return b      

算法說明

這題有幾乎相同的類似題，可參考：

【Leetcode】python – [Google | Onsite] Two Sum – Closest to Target 個人解法筆記 (Lintcode – 533)

前者是 2Sum，這題更難改成 3Sum，但思路與 3Sum 大同小異

【Leetcode】python – [15] 3Sum 個人解法筆記 (updated: 2022/4/6)

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

input handling

處理 input 為 [] 或 len < 3 的情況，輸出 -1 。(題目沒說，但這邊先預留特殊狀況處理)

Boundary conditions

特別留意 3Sum 的搜尋條件，特別是 a <= b <= c 的處理部分 (可以看 3Sum 的文章)

Reference

• 最接近的三数之和 · 3Sum Closest
• 【Leetcode】python – [15] 3Sum 個人解法筆記 (last update: 2022/4/6)
• 【Leetcode】python – [Google | Onsite] Two Sum – Closest to Target 個人解法筆記 (Lintcode – 533)