3 Sum的變形

題目連結: 16. 3Sum Closest

題目描述:給定一個長度為 n 的整數數組 nums 和一個整數目標，找出 nums 中的三個整數，使它們的和最接近目標。返回這三個整數的和。

Python

與 3Sum 的主要區別：

• 目標不同：3Sum 要求 和 == 0；3Sum Closest 要求 abs(和 - target) 最小。

• 返回值不同：3Sum 返回所有滿足條件且不重複的三元組；3Sum Closest 只返回那個最接近 target 的和（一個整數）。

• 去重：3Sum 需要複雜的去重邏輯；3Sum Closest 因為只返回一個值，所以不需要處理重複的三元組。

排序+雙指針

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        min_diff = 10000
        ans = nums[0]+nums[1]+nums[2]
        for i in range(n-2):
            x = nums[i]
            left = i+1
            right = n-1
            while left<right:
                temp = x + nums[left] + nums[right]
                curr = abs(temp-target)
                if curr<min_diff:
                    min_diff = curr
                    ans = temp
                if temp<target:
                    left+=1
                elif temp>target:
                    right-=1
                else:
                    return target
        return ans
                

演算法分析:

• 先對陣列進行排序，排序後，陣列變為有序。
• 我們需要一個變數來記錄「目前找到的最接近 target 的和」。一個安全的初始值可以是陣列前三個元素的和。
• 在 while 迴圈中，比較「當前和與 target 的差距」和「已知最接近的和與 target 的差距」。
• 如果當前的和更接近，就更新ans。
• 移動指針的概念跟3 Sum一樣，和太小了移動left，反之，移動right，如果和與target差 ==0 則返回target。

複雜度分析:
* 排序佔用了O(n log n)，後面邏輯佔用了O(n^2)，所以時間複雜度為O(n^2)。
* 空間複雜度為O(1)(若考慮排序結果則空間複雜度為O(n)。

希望你們對於Two Pointers的題型能夠更理解!
今天就介紹到這邊，有問題都可以留言
下回見!