16. 3Sum Closest Medium
Given an integer array nums of length n 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 1:
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).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Approach
Input: An integer array nums, a target value target.
Output: Find the sum of three numbers that is closest to target and return it.
This is a classic problem of sorting + opposite-direction two pointers.
This problem is similar to 3Sum. We need to sort the array first, then fix one number, and use left and right pointers on the right side of this number to continuously find the combination of three numbers whose sum is closest to target.
Each time, calculate the sum of the current combination currentSum and update the sum that is closest to target closestSum.
If the current combination's sum is smaller than target, it means we need to move the left pointer to make the total sum larger.
If it is larger than target, move the right pointer to make the total sum smaller.
If we find a sum exactly equal to target, we can directly return target.
Finally, after the traversal is complete, return the recorded closest sum closestSum.
Implementation
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
# Sort the array first to prepare for using two pointers
nums.sort()
n = len(nums)
# Initialize a closest sum, set it to infinity
closest_sum = float('inf')
# Traverse the array, fixing one number nums[i] each time
for i in range(n - 2):
left = i + 1 # Left pointer starts from the right of i
right = n - 1 # Right pointer starts from the end of the array
# Use two pointers moving towards the center to find the sum of three numbers closest to target
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
# If the current sum of three numbers is closer to target than the previously recorded one, update closest_sum
if abs(target - current_sum) < abs(target - closest_sum):
closest_sum = current_sum
# Move pointers based on the comparison of the current sum and the target value
if current_sum < target:
left += 1 # The current sum is too small, move left pointer right to increase the total sum
elif current_sum > target:
right -= 1 # The current sum is too large, move right pointer left to decrease the total sum
else:
# If it is exactly equal to the target value, it means it is already the optimal solution, return directly
return target
# Return the final sum of three numbers closest to the target value
return closest_sum/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
nums.sort((a, b) => a - b);
let closestSum = Infinity;
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const currentSum = nums[i] + nums[left] + nums[right];
if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
closestSum = currentSum
}
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return target;
}
}
}
return closestSum;
};Complexity Analysis
- Time Complexity: O(n^2)
- Space Complexity: O(1)