Skip to content

LeetCode: 16-3Sum Closest 解題紀錄

Last Updated on 2021-07-28 by Clay

題目

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

這個題目跟 15 題非常相似，同樣是給定一組整數陣列輸入，不過還多給了一個目標值 target。我們需要找出 3 個數值，使其加總值越接近 target 越好。

需要注意的是，我們要返回的並不是找到的陣列，而是直接返回最接近 target 的數值。

解題思路

解題方法與第 15 題十分接近。

  • 先將陣列由小到大排序（感謝網友提醒！原先將順序寫反了）
  • 使用迴圈讀出第 i 個值，同時設定 left 以及 right 兩端座標
    • left 從 i+1 開始計算
    • right 從陣列長度-1 開始計算
  • 計算第 i 個值、第 left 個值、第 right 個值加總
    • 等於 target：直接返回 target 值即可
    • 小於 target：代表加總值不夠大，將 left 點往右移動，尋更大的值
    • 大於 target：代表加總值太大，將 right 點往左移動，尋找更小的值
  • 計算過程中，隨時將與 target 距離最近的數值保存下來，迴圈結束後便返回該值


C++ 程式碼

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // Init
        int min_d = NULL;
        int closest_v = NULL;
        
        // Sort
        sort(nums.begin(), nums.end());
        
        // Find the minimum distance
        for (int i=0; i<nums.size(); ++i) {
            int left = i + 1;
            int right = nums.size()-1;
            
            while (left < right) {
                int temp_v = nums[i] + nums[left] + nums[right];
                int temp_d = target - temp_v;
                
                if (temp_d < 0) temp_d *= -1;
                
                if (min_d == NULL or temp_d < min_d) {
                    min_d = temp_d;
                    closest_v = temp_v;
                }
                
                // Move
                if (temp_v < target) {
                    ++left;
                }
                else if (temp_v > target) {
                    --right;
                }
                else if (temp_v == target) {
                    return target;
                }
            }
        }
        
        return closest_v;
    }
};


Python 程式碼

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # Init
        min_d = None
        closest_v = None
        
        # Sort
        nums.sort()
        
        # Find the cloest value
        for i in range(len(nums)):
            left = i + 1
            right = len(nums) - 1
            
            while left < right:
                temp_v = nums[i] + nums[left] + nums[right]
                temp_d = target - temp_v
                if temp_d < 0: temp_d *= -1
                
                if not min_d or (temp_d < min_d):
                    min_d = temp_d
                    closest_v = temp_v
                    
                # Move the boundary
                if temp_v > target:
                    right -= 1
                elif temp_v < target:
                    left += 1
                elif temp_v == target:
                    return target
        
        # Return
        return closest_v


References

Tags:

2 thoughts on “LeetCode: 16-3Sum Closest 解題紀錄”

Leave a Reply取消回覆

Exit mobile version