Description:
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.
Examples:
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).Solution in Python:
To solve the problem of finding three integers in an array such that their sum is closest to a given target, we can use a two-pointer approach after sorting the array. This approach ensures that we efficiently find the closest sum without needing to check all possible combinations explicitly.
Python
from typing import List
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
# First, sort the array
nums.sort()
# Initialize the closest sum to the sum of the first three elements
closest_sum = nums[0] + nums[1] + nums[2]
# Iterate through the array, considering each element as a potential first element of the triplet
for i in range(len(nums) - 2):
# Use two pointers to find the best pair for the current element
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
# If the current sum is exactly the target, we can return immediately
if current_sum == target:
return current_sum
# Update the closest sum if the current sum is closer to the target
if abs(current_sum - target) < abs(closest_sum - target):
closest_sum = current_sum
# Move the pointers based on the comparison between current_sum and target
if current_sum < target:
left += 1
else:
right -= 1
return closest_sumDetailed Comments on the Code:
- Sorting the Array:
- The first step is to sort the input array. Sorting helps us to use the two-pointer technique effectively.
- Initialization:
- We initialize
closest_sumto a very large value (float('inf')). This will store the closest sum we have found so far.
- We initialize
- Main Loop:
- We iterate through the array with index
ifrom0tolen(nums) - 2. This loop considers each element as the potential first element of the triplet. - For each
i, we use two pointersleftandrightto find the other two elements of the triplet:leftstarts just afteri(i + 1).rightstarts at the end of the array.
- We iterate through the array with index
- Two-Pointer Technique:
- Inside the main loop, we enter a while loop where
left < right. - Calculate the
current_sumof the triplet (nums[i] + nums[left] + nums[right]). - If
current_sumexactly matches the target, we immediately returncurrent_sum. - If
current_sumis closer to the target than the previous closest sum, we updateclosest_sum. - Depending on whether
current_sumis less than or greater than the target, we move theleftorrightpointer respectively to try to get closer to the target.
- Inside the main loop, we enter a while loop where
- Return the Closest Sum:
- After the loops finish, we return
closest_sum, which holds the sum of the triplet closest to the target.
- After the loops finish, we return
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
// First, sort the array to use the two-pointer technique
nums.sort((a, b) => a - b);
// Initialize the closest sum to the sum of the first three elements
let closestSum = nums[0] + nums[1] + nums[2];
// Iterate through the array, considering each element as a potential first element of the triplet
for (let i = 0; i < nums.length - 2; i++) {
// Use two pointers to find the best pair for the current element
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
let currentSum = nums[i] + nums[left] + nums[right];
// If the current sum is exactly the target, we can return immediately
if (currentSum === target) {
return currentSum;
}
// Update the closest sum if the current sum is closer to the target
if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
closestSum = currentSum;
}
// Move the pointers based on the comparison between currentSum and target
if (currentSum < target) {
left++;
} else {
right--;
}
}
}
return closestSum;
};Solution in Java:
Java
import java.util.Arrays;
class Solution {
public int threeSumClosest(int[] nums, int target) {
// First, sort the array to use the two-pointer technique
Arrays.sort(nums);
// Initialize the closest sum to the sum of the first three elements
int closestSum = nums[0] + nums[1] + nums[2];
// Iterate through the array, considering each element as a potential first element of the triplet
for (int i = 0; i < nums.length - 2; i++) {
// Use two pointers to find the best pair for the current element
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
// If the current sum is exactly the target, we can return immediately
if (currentSum == target) {
return currentSum;
}
// Update the closest sum if the current sum is closer to the target
if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
closestSum = currentSum;
}
// Move the pointers based on the comparison between currentSum and target
if (currentSum < target) {
left++;
} else {
right--;
}
}
}
return closestSum;
}
}Solution in C#:
C#
using System;
public class Solution {
public int ThreeSumClosest(int[] nums, int target) {
// First, sort the array to use the two-pointer technique
Array.Sort(nums);
// Initialize the closest sum to the sum of the first three elements
int closestSum = nums[0] + nums[1] + nums[2];
// Iterate through the array, considering each element as a potential first element of the triplet
for (int i = 0; i < nums.Length - 2; i++) {
// Use two pointers to find the best pair for the current element
int left = i + 1;
int right = nums.Length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
// If the current sum is exactly the target, we can return immediately
if (currentSum == target) {
return currentSum;
}
// Update the closest sum if the current sum is closer to the target
if (Math.Abs(currentSum - target) < Math.Abs(closestSum - target)) {
closestSum = currentSum;
}
// Move the pointers based on the comparison between currentSum and target
if (currentSum < target) {
left++;
} else {
right--;
}
}
}
return closestSum;
}
}