Problem Statement
Given an array of unsorted integers a
and a target
, find a triplet in the array whose sum is closest to the target value. Return the sum of the triplet.
Example 1:
Input: a[] = [-2, -4, 6, 3, 7], target = 2
Output: 1
Explanation: Triplet with sum closest to target is [-2, -4, 7], sum of the triplets = 1
Example 2:
Input: a[] = [10, 2, 30, 49, 8], target = 50
Output: 48
Explanation: Triplet with sum closest to target is [10, 30, 8], sum of the triplets = 48
Example 2:
Input: a[] = [1, 0, 5, 0, 3], target = 100
Output: 9
Solution
Two-pointer approach
import java.util.Arrays;
import java.util.Scanner;
public class TripletSumClosestToTarget {
private static int findTripletSumClosestToTarget(int[] a, int targetSum) {
Arrays.sort(a);
int smallestDiff = Integer.MAX_VALUE;
for(int i = 0; i < a.length-2; i++) {
// Skip duplicates
if(i > 0 && a[i] == a[i-1]) {
continue;
}
// Fix one number
int firstNum = a[i];
// Use Two-sum approach to get the other two numbers
// such that the sum of all three numbers are closest to target
int left = i+1, right = a.length-1;
while(left < right) {
int currentSum = firstNum + a[left] + a[right];
int currentDiff = targetSum-currentSum;
if(currentDiff == 0) {
return currentSum;
}
if(Math.abs(currentDiff) < Math.abs(smallestDiff)) {
smallestDiff = currentDiff;
}
if (currentDiff > 0) {
// TargetSum is greater than the sum of triplets.
// Increment left pointer to increase the sum so that the difference moves closer to zero
left++;
} else {
// TargetSum is smaller than the sum of triplets.
// Decrement right pointer to decrease the sum so that the difference moves closer to zero
right--;
}
}
}
return targetSum-smallestDiff;
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int targetSum = keyboard.nextInt();
keyboard.close();
System.out.printf("Triplet sum closest to target = %d%n", findTripletSumClosestToTarget(a, targetSum));
}
}