[LeetCode解題攻略] 16. 3Sum Closest

題目描述

給定一個長度為 n 的整數數組 nums 和一個整數target，在 nums 中找到三個整數，使得總和最接近target。傳回三個整數的總和。可以假設每個輸入都有一個解決方案。

1. 範例 1：

   Input: nums = [-1, 2, 1, -4], target = 1
   Output: 2
   Explanation: 最接近目標值 1 的三元組為 [-1, 2, 1]，其和為 2。

2. 範例 2：

   Input: nums = [0, 0, 0], target = 1
   Output: 0
   Explanation: 三數之和為 0，最接近目標值 1。

解題思路

本題的目標是找到和最接近 target 的三元組，類似於 3Sum 問題，但這次我們不需要找出所有符合條件的三元組，而是找到最接近的和。

我們可以採用以下策略來解決這個問題：

1. 暴力解法：枚舉所有三元組，計算它們的和並更新最接近目標的結果。
2. 排序 + 雙指針：將陣列排序後，利用雙指針的優化來有效縮小搜尋範圍。

解法 1：暴力解法

思路

• 使用三層迴圈，枚舉所有可能的三元組，計算每個三元組的和與 target 的差值。
• 逐一比較並更新最接近的和。

實現 (Python)

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        closest_sum = float('inf')  # 初始化為無限大

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    current_sum = nums[i] + nums[j] + nums[k]
                    # 如果目前的和比之前更接近目標，則更新結果
                    if abs(current_sum - target) < abs(closest_sum - target):
                        closest_sum = current_sum

        return closest_sum

時間與空間複雜度

• 時間複雜度：O(n³)，三層迴圈遍歷所有可能的三元組。
• 空間複雜度：O(1)，除了變數儲存外，無額外空間使用。

解法 2：排序 + 雙指針

思路

1. 排序陣列：先將陣列排序，這樣可以方便使用雙指針技巧。
2. 固定一個數字，然後在剩下的陣列中尋找最接近的兩數和：
3. • 遍歷陣列中的每個數字作為固定值 nums[i]。
   • 使用雙指針在剩下的陣列中尋找最接近 target - nums[i] 的兩數和。
3. 更新結果：比較每組三元組的和與目標值的接近程度，並更新結果。

實現 (Python)

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()  # 將陣列排序
        closest_sum = float('inf')  # 初始化為無限大
        n = len(nums)

        for i in range(n):
            left, right = i + 1, n - 1  # 雙指針
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                # 更新最接近的和
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                # 根據 current_sum 與 target 的大小調整指針
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum  # 如果剛好等於 target，直接返回

        return closest_sum

時間與空間複雜度

• 時間複雜度：O(n²)
• • 排序的時間複雜度為 O(n log n)，雙指針遍歷的時間複雜度為 O(n²)，總計 O(n²)。
• 空間複雜度：O(1)
• • 除了排序外，僅需使用額外變數儲存指針與結果。

總結

排序 + 雙指針 是本題的最佳解法，因為它在時間效率和實現簡潔性之間達到了很好的平衡。希望這篇詳細的教學能幫助你理解並解決這個問題！