16. 3Sum Closest
給定一個長度為 n 的整數數組 nums 和一個整數目標值 target，找出 nums 中的三個整數，使其和最接近 target。
返回這三個整數的和。
你可以假設每個輸入都只有一個解。
範例 1：
輸入：nums = [-1,2,1,-4], target = 1 輸出：2 解釋：最接近目標值的和是 2。(-1 + 2 + 1 = 2)。
Python
from typing import List
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
# Sort the array to use the two-pointer technique
nums.sort()
closest_sum = float('inf') # Initialize with a large value
for i in range(len(nums)):
# Use two pointers to find the closest sum
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
# If the current sum is closer to the target, update closest_sum
if abs(current_sum - target) < abs(closest_sum - target):
closest_sum = current_sum
if current_sum < target:
left += 1
elif current_sum > target:
right -= 1
else:
# If the current sum is exactly equal to the target, return it
return current_sum
return closest_sum
16.52MB, 405ms
C++
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
// Sort the array to use the two-pointer technique
sort(nums.begin(), nums.end());
int closest_sum = numeric_limits<int>::max() / 2; // Initialize to a large
value to avoid overflow
for (int i = 0; i < nums.size() - 2; ++i) {
// Use two pointers to find the closest sum
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int current_sum = nums[i] + nums[left] + nums[right];
// If the current sum is closer to the target, update closest_sum
if (abs(current_sum - target) < abs(closest_sum - target)) {
closest_sum = current_sum;
}
if (current_sum < target) {
++left;
} else if (current_sum > target) {
--right;
} else {
// If the current sum is exactly equal to the target, return it
return current_sum;
}
}
}
return closest_sum;
}
};
12.78MB, 7ms
Javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
// Sort the array to use the two-pointer technique
nums.sort((a, b) => a - b);
let closest_sum = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
let current_sum = nums[i] + nums[left] + nums[right];
// If the current sum is closer to the target, update closest_sum
if (Math.abs(current_sum - target) < Math.abs(closest_sum - target)) {
closest_sum = current_sum;
}
if (current_sum < target) {
left++;
} else if (current_sum > target) {
right--;
} else {
// If the current sum is exactly equal to the target, return it
return current_sum;
}
}
}
return closest_sum;
};
50.74ms, 71ms
