Problem Statement: 3Sum Closest
Description: Given an integer array nums of length n, and an integer target, you need to find three integers in the array such that their sum is closest to the target. Return the sum of the three integers.
Note:
- You may assume that each input would have exactly one solution.
- The sum can be greater than or less than the target.
Constraints:
3 <= nums.length <= 1000-10^3 <= nums[i] <= 10^3-10^3 <= target <= 10^3
Approach:
- Sorting:
- First, sort the array. Sorting will help efficiently check for the closest sum using a two-pointer technique.
- Two-pointer Technique:
- Iterate over the array with one pointer (let’s call it
i), fixing the first element. - For each fixed element, use the two-pointer approach to find the closest sum. The second pointer (
left) starts just afteri, and the third pointer (right) starts at the end of the array. - If the sum of the triplet is equal to the target, return the sum immediately.
- If the sum is less than the target, move the
leftpointer rightward to increase the sum. - If the sum is greater than the target, move the
rightpointer leftward to decrease the sum. - Track the closest sum encountered during this process and update the result accordingly.
- Iterate over the array with one pointer (let’s call it
- Time Complexity:
- Sorting the array takes O(n log n), and the two-pointer search for each element takes O(n). Hence, the overall time complexity is O(n^2).
- Space Complexity:
- O(1), since we are only using a few variables to track the closest sum.
Example:
For input:
nums = [-1, 2, 1, -4], target = 1
Output:
2
Explanation: The sum that is closest to 1 is (-1 + 2 + 1 = 2).
Code Implementation in Different Languages:
C:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int threeSumClosest(int* nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), compare);
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < numsSize - 2; i++) {
int left = i + 1, right = numsSize - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (abs(sum - target) < abs(closest - target)) {
closest = sum;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return sum;
}
}
}
return closest;
}
int main() {
int nums[] = {-1, 2, 1, -4};
int size = sizeof(nums) / sizeof(nums[0]);
int target = 1;
printf("Closest sum: %d\n", threeSumClosest(nums, size, target));
return 0;
}
C++:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.size() - 2; i++) {
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (abs(sum - target) < abs(closest - target)) {
closest = sum;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return sum;
}
}
}
return closest;
}
int main() {
vector<int> nums = {-1, 2, 1, -4};
int target = 1;
cout << "Closest sum: " << threeSumClosest(nums, target) << endl;
return 0;
}
Java:
import java.util.*;
public class Main {
public static int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < Math.abs(closest - target)) {
closest = sum;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return sum;
}
}
}
return closest;
}
public static void main(String[] args) {
int[] nums = {-1, 2, 1, -4};
int target = 1;
System.out.println("Closest sum: " + threeSumClosest(nums, target));
}
}
Python:
def threeSumClosest(nums, target):
nums.sort()
closest = nums[0] + nums[1] + nums[2]
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if abs(total - target) < abs(closest - target):
closest = total
if total < target:
left += 1
elif total > target:
right -= 1
else:
return total
return closest
# Example usage
nums = [-1, 2, 1, -4]
target = 1
print(threeSumClosest(nums, target))
JavaScript:
function threeSumClosest(nums, target) {
nums.sort((a, b) => a - b);
let closest = nums[0] + nums[1] + nums[2];
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1, right = nums.length - 1;
while (left < right) {
let sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < Math.abs(closest - target)) {
closest = sum;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return sum;
}
}
}
return closest;
}
// Example usage
let nums = [-1, 2, 1, -4];
let target = 1;
console.log(threeSumClosest(nums, target));
C#:
using System;
class Program {
public static int ThreeSumClosest(int[] nums, int target) {
Array.Sort(nums);
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.Length - 2; i++) {
int left = i + 1, right = nums.Length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.Abs(sum - target) < Math.Abs(closest - target)) {
closest = sum;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return sum;
}
}
}
return closest;
}
static void Main() {
int[] nums = {-1, 2, 1, -4};
int target = 1;
Console.WriteLine("Closest sum: " + ThreeSumClosest(nums, target));
}
}
Conclusion:
The 3Sum Closest problem can be efficiently solved using the two-pointer technique after sorting the array. The solution works in O(n^2) time complexity, making it suitable for large input sizes. By iterating over each element and adjusting the two pointers, we are able to track the closest sum to the target value.