[LeetCode][Medium] 16. 3Sum Closest

Leetcode 網址: https://leetcode.com/problems/3sum-closest/

題目說明:

給定 n 個整數與一個 target，請從這 n 個整數中找出 3 個數字 a, b, c 使得 a + b + c 最接近 target。

Note: 你可以假設這 n 個整數中只有唯一解。

解題說明:

這題只是 3sum 的變形，所以參考 3sum 的解法 即可解決此題。

程式碼

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int minDiff = INT_MAX;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            int left = i + 1, right = nums.size() - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                minDiff = abs(minDiff) > abs(target - sum) ? target - sum : minDiff;
                if (sum > target) right--;
                else if (sum < target) left++;
                else break;
            }
        }
        
        return target - minDiff;
    }
};

結果

Runtime: 8 ms, faster than 91.21% of C++ online submissions for 3Sum Closest.

Memory Usage: 9.8 MB, less than 94.01% of C++ online submissions for 3Sum Closest.