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).
Constraints:
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-104 <= target <= 104
Problem Description
The LeetCode problem asks us to find three numbers within an array nums such that their sum is closest to a given target value. The array nums has a length n, and it’s guaranteed that there is exactly one solution for each input.
To solve this problem, we must search for triplets in the array whose sum has the smallest absolute difference from the target. The final result is not the triplet itself, but rather the sum of its components.
Intuition
The intuition behind the provided solution leverages a sorted array and a two-pointer technique for efficient searching. Here’s a step-by-step breakdown of the approach:
- Sorting: We first sort the
numsarray. Sorting is crucial because it allows us to efficiently sweep through the array using two pointers and easily adjust the sum of the current triplet to get closer to thetarget. - Iterating with Three Pointers: We use a for-loop to iterate over the array with an index
irepresenting the first number of the triplet. The other two pointers,jandk, are initialized to the next element afteriand the last element of the array, respectively. The three numbers represented byi,j, andkare our current candidates for the closest sum. - Evaluating Sums and Moving Pointers: In the while-loop, we calculate the sum of the triplet (
t) and compare it to thetarget. If the sum exactly matches thetarget, we immediately return it.If the sum doesn’t match, we compare the absolute difference oftandtargetwith the current closest sum (ans), and if it’s smaller, we updateans.To search through different sums, we move pointersjandkdepending on whether the current sum is greater than or less thantarget. If it’s greater, we decrementkto reduce the sum. If it’s less, we incrementjto increase the sum. This is possible without missing the potential answers because the array is sorted.
By analyzing the difference between t and target and adjusting j and k accordingly, we can efficiently find the triplet with the sum that has the smallest absolute difference to the target.
- Returning the Answer: Once we’ve finished iterating through all possible triplets, we return the closest sum recorded as
ans.
Solution Approach
The algorithm implementation utilizes several important concepts and patterns:
- Sorting: The array is initially sorted to simplify the searching process. By having the array in ascending order, we can make use of the two-pointer technique effectively.
- Two-Pointer Technique: After fixing one number of the potential triplet using the first for-loop, the two other numbers are controlled by two pointers. One starts right after the fixed element (
j), while the other starts from the end of the array (k). These pointers move closer to each other as they iterate. - Avoiding Redundancy: Since each number in
numsis used as a starting point for a triplet, the solution avoids re-examining numbers that are identical to the previous starting point (iposition) by skipping duplicate combinations. (This is implicit and can be added to optimization in the code if necessary by checking for the same numbers when incrementingi). - Closest Sum Calculation: As the pointers
jandkmove, the solution calculates the sum of the three numbers, compares it with thetarget, and keeps track of the closest sum encountered by comparing the absolute differences with the current best answer (ans). - Conditional Pointer Movement: Based on whether the current sum is greater than or less than
target,kis decremented orjis incremented respectively. This allows the solution to narrow down the closest sum without checking all possible triplet combinations, which would result in higher computational complexity. - Early Termination: If at any point the sum equals the target, the loop breaks and returns the sum immediately since it cannot get any closer than an exact match.
- Return Statement: After going through all possible iterations, the algorithm returns the sum stored in
ans, which is the closest sum totargetthat the solution could find during the iteration process.
The code uses a simple inf value to initialize ans so that any other sum found will be closer compared to infinity. Utilizing this approach, the data structure (a single array) is kept simple, and the algorithm achieves a time complexity of O(n^2), since it only involves iterating over the array of length n and adjusting the pointers without nested full iterations.
Example Walkthrough
Let’s consider a small example to illustrate the solution approach using the strategy detailed in the content provided.
Suppose we have the following nums array and target:
nums = [-1, 2, 1, -4]
target = 1Firstly, according to our approach, we need to sort the nums:
sorted_nums = [-4, -1, 1, 2]Now we iterate through sorted_nums with our three pointers. For simplicity, I’ll walk through the first complete iteration:
- Set
i = 0, which is the value-4. This is our first number of the potential triplet. - Initialize two other pointers,
j = i + 1=>j = 1(value-1) andk = n - 1=>k = 3(value2). - We then enter a while loop with
j < kand calculate the sumtusingsorted_nums[i],sorted_nums[j], andsorted_nums[k]. So, our first sum ist = (-4) + (-1) + (2) = -3. - Since our goal is to get the sum close to
target(1), we check the absolute difference betweentandtarget. Abs(-3 - 1) = Abs(-4) = 4. - We initialize our answer
answith infinity. Our first comparison will setans = -3as it’s the closest sum we’ve encountered. tis less thantarget, we incrementjto increase the sum. Now,j = 2(value1).- Calculate a new sum:
t = (-4) + (1) + (2) = -1. - Compare the new sum’s absolute difference with
target. Abs(-1 - 1) = 2, which is closer to the target than our previous best of 4. Updateansto-1. - Since
-1is still less than thetarget, we incrementjonce again. Now,j = 3which is equal tok, so we break out of the while-loop. - The loop for the index
icontinues, but for the sake of brevity, let’s assume the remaining iterations do not find a sum closer to the target than the sum whenanswas-1.
With these steps completed, we assert that the closest sum to the target we have found using this method is -1. As per our algorithm’s implementation, -1 will be the final answer returned.
Note that for a real implementation, the process would involve iterating over all valid i, j, and k combinations until the end of the array is reached, continuously updating ans if closer sums are found, and potentially breaking early if an exact match is found. However, this simple example serves to convey the essentials of the solution approach.
Solution Implementation
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end()); // Sort the array to apply the two-pointer technique
int ans = nums[0] + nums[1] + nums[2]; // Initialize the answer with the first possible triplet sum
// Iterate through the array to find the closest sum
for (int i = 0; i < nums.size() - 2; i++) {
int j = i + 1; // Initialize the left pointer just after the current element
int k = nums.size() - 1; // Initialize the right pointer at the end of the array
// Use the two-pointer technique to find the closest sum
while (j < k) {
int sum = nums[i] + nums[j] + nums[k]; // Calculate the sum of the current triplet
if (sum == target) {
return sum; // If the sum is exactly equal to the target, return it immediately
}
// Update the answer if the current sum is closer to the target
if (abs(sum - target) < abs(ans - target)) {
ans = sum;
}
// If the sum is greater than the target, move the right pointer to the left
else if (sum > target) {
k--;
}
// If the sum is less than the target, move the left pointer to the right
else {
j++;
}
}
}
return ans; // Return the closest sum found
}
};Copied!
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); // Sort the array to apply the two-pointer technique
int res = Integer.MAX_VALUE; // Initialize the result to the maximum possible value
// Iterate through the array to find the closest sum
for(int i = 0; i < nums.length; i++) {
int s = i + 1; // Initialize the left pointer just after the current element
int e = nums.length - 1; // Initialize the right pointer at the end of the array
// Use the two-pointer technique to find the closest sum
while(s < e) {
int current = nums[i] + nums[s] + nums[e]; // Calculate the sum of the current triplet
if(current > target) {
e--; // If the sum is greater than the target, move the right pointer to the left
} else {
s++; // If the sum is less than or equal to the target, move the left pointer to the right
}
// Update the result if the current sum is closer to the target
if(Math.abs(current - target) < Math.abs(res - target)) {
res = current;
}
}
}
return res; // Return the closest sum found
}
}Copied!
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort() # Sort the array to apply the two-pointer technique
closest_sum = float('inf') # Initialize closest_sum to a very large value
# Iterate through the array to find the closest sum
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1 # Initialize the left and right pointers
# Use two pointers to find the closest sum for the current element
while left < right:
current_sum = nums[i] + nums[left] + nums[right] # Calculate the sum of the current triplet
# Update closest_sum if the current sum is closer to the target
if abs(target - current_sum) < abs(target - closest_sum):
closest_sum = current_sum
# Move the pointers based on the comparison of the current sum and target
if current_sum < target:
left += 1 # If the sum is smaller than the target, move the left pointer to the right
elif current_sum > target:
right -= 1 # If the sum is greater than the target, move the right pointer to the left
else:
return current_sum # If an exact match is found, return the sum immediately
return closest_sum # Return the closest sum found after iterating through all possibilitiesCopied!
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b); // Comparator function to sort integers in ascending order
}
int threeSumClosest(int* nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), compare); // Sort the array to use the two-pointer technique
int closest = nums[0] + nums[1] + nums[2]; // Initialize closest with the sum of the first three elements
// Iterate through the array to find the closest sum
for (int i = 0; i < numsSize - 2; i++) {
int left = i + 1; // Initialize left pointer just after the current element
int right = numsSize - 1; // Initialize right pointer at the end of the array
// Use two-pointer technique to find the closest sum for the current element
while (left < right) {
int sum = nums[i] + nums[left] + nums[right]; // Calculate the sum of the current triplet
// Update closest if the current sum is closer to the target
if (abs(target - sum) < abs(target - closest)) {
closest = sum;
}
// Move the pointers based on the comparison of the current sum and target
if (sum < target) {
left++; // If the sum is smaller than the target, move the left pointer to the right
} else if (sum > target) {
right--; // If the sum is greater than the target, move the right pointer to the left
} else {
return sum; // If an exact match is found, return the sum immediately
}
}
}
return closest; // Return the closest sum found after iterating through all possibilities
}Copied!
public class Solution {
// Main function to find the closest sum to the target
public int ThreeSumClosest(int[] nums, int target)
{
// Shuffle the array to randomize the input (optional for this algorithm)
Suffle(nums);
// Sort the array using a 3-way quicksort technique
Quick3WaySort(nums, 0, nums.Length - 1);
int result = 0, rest = int.MaxValue;
int sumValue = 0;
var tempRest = 0;
int lo = 0, hi = 0;
// Loop through the array, treating each element as a potential first element of a triplet
for (var index = 0; index < nums.Length - 2; index++)
{
lo = index + 1; // Left pointer starts just after the current element
hi = nums.Length - 1; // Right pointer starts at the end of the array
// Use two pointers to find a triplet sum
while (lo < hi)
{
sumValue = nums[index] + nums[lo] + nums[hi]; // Calculate the sum of the triplet
tempRest = target - sumValue; // Calculate the difference from the target
if (tempRest == 0) { return sumValue; } // If exact match, return the sum immediately
tempRest = tempRest < 0 ? -tempRest : tempRest; // Convert the rest to positive for comparison
// Update the closest sum if this sum is closer to the target
if (tempRest < rest)
{
rest = tempRest;
result = sumValue;
}
// Move the pointers based on the current sum compared to the target
if (sumValue < target)
{
do
{
lo++; // If the sum is too small, move the left pointer to the right
} while (lo < hi && nums[lo - 1] == nums[lo]); // Skip duplicates on the left
}
else if (sumValue > target)
{
do
{
hi--; // If the sum is too large, move the right pointer to the left
} while (lo < hi && nums[hi + 1] == nums[hi]); // Skip duplicates on the right
}
else
{
// If the sum matches the target, move both pointers to skip duplicates
do
{
lo++;
} while (lo < hi && nums[lo - 1] == nums[lo]);
do
{
hi--;
} while (lo < hi && nums[hi + 1] == nums[hi]);
}
}
// Skip duplicate elements for the first element of the triplet
while (index < nums.Length - 3 && nums[index + 1] == nums[index])
{
index++;
}
}
return result; // Return the closest sum found
}
// Helper function to shuffle the array
void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
for (int i = 0; i < N; i++)
{
r = random.Next(i + 1); // Generate a random index to swap
// Swap the elements at index i and r
temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}
// QuickSort with a 3-way partitioning for sorting the array
void Quick3WaySort(int[] nums, int lo, int hi)
{
if (lo >= hi) { return; } // Base case: return if the segment is empty or a single element
var lt = lo;
var gt = hi;
var i = lo;
var v = nums[i]; // Pivot value (first element)
int temp;
// Partition the array around the pivot value
while (i <= gt)
{
if (nums[i] > v) // If current element is greater than the pivot, move it to the high end
{
temp = nums[i];
nums[i] = nums[gt];
nums[gt--] = temp;
}
else if (nums[i] < v) // If current element is smaller than the pivot, move it to the low end
{
temp = nums[i];
nums[i] = nums[lt];
nums[lt++] = temp;
}
else
{
i++; // If current element is equal to the pivot, move to the next element
}
}
// Recursively sort the two subarrays
Quick3WaySort(nums, lo, lt - 1);
Quick3WaySort(nums, gt + 1, hi);
}
}Copied!
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
// Sort the array in ascending order to use the two-pointer technique
nums.sort((a,b)=>a-b);
// Initialize the closest sum to Infinity (a very large number)
let closest = Infinity;
// Loop through the array, treating each element as the first element of the triplet
for (let i = 0; i < nums.length - 2; i++) {
// Use two pointers, one starting from the next element and the other from the end
let left = i + 1;
let right = nums.length - 1;
// While the left pointer is before the right pointer, calculate the sum
while (left < right) {
let localSum = nums[i] + nums[left] + nums[right];
// If the current sum is closer to the target, update the closest sum
if (Math.abs(localSum - target) < Math.abs(closest - target)) closest = localSum;
// If the sum is greater than the target, move the right pointer to the left
if (localSum > target) right--;
// If the sum is less than the target, move the left pointer to the right
else left++;
}
}
// Return the closest sum found
return closest;
};Copied!
function threeSumClosest(nums: number[], target: number): number {
// Sort the array in ascending order for two-pointer technique
nums.sort((a, b) => a - b);
// Initialize the answer as a large number (use bitwise shift for max value)
let ans: number = 1 << 30;
// Get the length of the input array
const n = nums.length;
// Iterate through the array, treating each element as the first element of the triplet
for (let i = 0; i < n; ++i) {
let j = i + 1; // Left pointer starts just after the current element
let k = n - 1; // Right pointer starts at the end of the array
// Use two pointers to find the sum closest to the target
while (j < k) {
const t: number = nums[i] + nums[j] + nums[k]; // Calculate the sum of the triplet
// If the sum equals the target, return the sum as it's an exact match
if (t === target) {
return t;
}
// If the sum is closer to the target than the current closest sum, update ans
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
}
// If the sum is greater than the target, move the right pointer to the left
if (t > target) {
--k;
} else {
// If the sum is smaller than the target, move the left pointer to the right
++j;
}
}
}
// Return the closest sum found
return ans;
}Copied!
class Solution {
/**
* @param int[] $nums
* @param int $target
* @return int
*/
function threeSumClosest($nums, $target) {
$n = count($nums); // Get the number of elements in the array
$closestSum = $nums[0] + $nums[1] + $nums[2]; // Initialize the closest sum with the first triplet
$minDiff = abs($closestSum - $target); // Initialize the minimum difference with the difference between closestSum and target
sort($nums); // Sort the array in ascending order for the two-pointer approach
// Iterate through the array with the first pointer
for ($i = 0; $i < $n - 2; $i++) {
$left = $i + 1; // Initialize the left pointer just after the current element
$right = $n - 1; // Initialize the right pointer at the end of the array
// Use two pointers to find the closest sum
while ($left < $right) {
$sum = $nums[$i] + $nums[$left] + $nums[$right]; // Calculate the current sum of the triplet
$diff = abs($sum - $target); // Find the difference between the current sum and the target
// If the difference is smaller than the current smallest difference, update the closest sum
if ($diff < $minDiff) {
$minDiff = $diff;
$closestSum = $sum;
}
// If the sum is less than the target, move the left pointer to the right to increase the sum
elseif ($sum < $target) {
$left++;
}
// If the sum is greater than the target, move the right pointer to the left to decrease the sum
elseif ($sum > $target) {
$right--;
}
// If the sum equals the target, return the sum immediately
else {
return $sum;
}
}
}
// Return the closest sum found
return $closestSum;
}
}Copied!
class Solution {
// Function to find the sum of three numbers closest to the target
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
// Sort the input array to use the two-pointer technique
let sorted = nums.sorted()
let length = sorted.count
// Initialize variables to keep track of the smallest difference and result
var diff: Int = .max
var result = 0
// Iterate through the sorted array, treating each element as the first element of the triplet
for i in 0..<length - 2 {
var n = i + 1, q = length - 1 // Initialize pointers: n for the left pointer and q for the right pointer
while n < q {
// Calculate the sum of the triplet
let sum = sorted[i] + sorted[n] + sorted[q]
// Move the pointer to get closer to the target sum
sum > target ? (q -= 1) : (n += 1)
// Calculate the absolute difference between the current sum and the target
let value = abs(sum - target)
// If this difference is smaller than the previous one, update the result
if value < diff {
diff = value
result = sum
}
}
}
// Return the sum of the triplet closest to the target
return result
}
}Copied!
class Solution {
// Function to find the sum of three numbers closest to the target
fun threeSumClosest(nums: IntArray, target: Int): Int {
// Initialize closerNumber with the sum of the first three numbers
var closerNumber = nums[0] + nums[1] + nums[2]
// Sort the input array for the two-pointer technique
val numsSorted = nums.sorted()
// Iterate through the sorted array, treating each element as the first element of the triplet
for (i in 0..numsSorted.lastIndex - 2) {
var left = i + 1 // Left pointer, starts just after the current element
var right = numsSorted.lastIndex // Right pointer, starts at the last element
// While the left pointer is less than the right pointer
while (left < right) {
// Calculate the sum of the current triplet
val sum = numsSorted[i] + numsSorted[right] + numsSorted[left]
// If the sum equals the target, return it immediately
if (sum == target) return sum
// If the current sum is closer to the target, update closerNumber
if (abs(target - sum) < abs(target - closerNumber)) {
closerNumber = sum
}
// Move pointers to try to get closer to the target
if (sum < target) {
left++ // If sum is less than target, move left pointer right
} else {
right-- // If sum is greater than target, move right pointer left
}
}
}
// Return the closest sum found
return closerNumber
}
}Copied!
class Solution {
// Function to find the sum of three numbers closest to the target
int threeSumClosest(List<int> nums, int target) {
// Initialize closest difference as the difference between the first triplet and the target
int closest = (nums[0] + nums[1] + nums[2] - target).abs();
// Initialize val to store the sum of the first triplet
int val = nums[0] + nums[1] + nums[2];
// Iterate through each triplet in the list
for(int i = 0 ; i < nums.length ; ++i){
for(int x = i + 1; x < nums.length ; ++x){
for(int z = x + 1; z < nums.length ; ++z){
// Calculate the absolute difference between the current triplet sum and the target
if((nums[i] + nums[x] + nums[z] - target).abs() < closest){
// If this triplet is closer to the target, update closest difference and val
closest = (nums[i] + nums[x] + nums[z] - target).abs();
val = nums[i] + nums[x] + nums[z];
}
}
}
}
// Return the triplet sum that is closest to the target
return val;
}
}Copied!
func threeSumClosest(nums []int, target int) int {
// Helper func
abs := func(num int) int {
if num < 0 {
return -num
}
return num
}
// Sort the input array in ascending order
sort.Ints(nums)
// Initialize the result variable with the sum of the first three elements
result := nums[0] + nums[1] + nums[2]
// Iterate through the array
for i := 0; i < len(nums)-2; i++ {
// Use two pointers approach
left := i + 1
right := len(nums) - 1
// Continue until the two pointers meet
for left < right {
// Calculate the sum of three elements
sum := nums[i] + nums[left] + nums[right]
// If the sum is equal to the target, return the sum
if sum == target {
return sum
}
// Update the result if the current sum is closer to the target
if abs(target-sum) < abs(target-result) {
result = sum
}
// Move the pointers based on the sum
if sum < target {
left++
} else {
right--
}
}
}
return result
}Copied!
Time and Space Complexity
Time Complexity
The time complexity of the given function depends on a few distinct steps:
- Sorting the array: The
sort()method in Python uses the Timsort algorithm, which has a time complexity ofO(n log n), wherenis the length of the list being sorted. - The for-loop: The loop runs for each element in the sorted array, resulting in a complexity of
O(n)iterations. - The while-loop inside the for-loop: In the worst case, for each iteration of the for-loop, the while-loop can perform nearly
O(n)operations since it might iterate fromi+1to then-1index.
Combining these complexities, the first step is dominant if n is large. However, since the nested loop inside the for-loop could potentially run n times for each n iterations of the for-loop, the resulting time complexity is O(n^2), since n(n-1)/2 simplifies to O(n^2). This nested loop is the most influential factor for large n.
So, the overall time complexity of the algorithm is O(n log n) + O(n^2), which simplifies to O(n^2) since the O(n^2) term is dominant for large n.
Space Complexity
The space complexity is O(1) if we ignore the space used for input and output since the sorting is done in-place and only a fixed number of variables are used, which does not scale with the size of the input array.