Triplet Sum close to target-CodePudding

Given an array of unsorted numbers and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return the sum of the triplet with the smallest sum.

Below is the code -

import java.util.*;

class TripletSumCloseToTarget {

  public static int searchTriplet(int[] arr, int targetSum) {
    if (arr == null || arr.length < 3)
      throw new IllegalArgumentException();

    Arrays.sort(arr);
    int smallestDifference = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length - 2; i  ) {
      int left = i   1, right = arr.length - 1;
      while (left < right) {
        // comparing the sum of three numbers to the 'targetSum' can cause overflow
        // so, we will try to find a target difference
        int targetDiff = targetSum - arr[i] - arr[left] - arr[right];
        if (targetDiff == 0) //  we've found a triplet with an exact sum
          return targetSum; // return sum of all the numbers

        // the second part of the above 'if' is to handle the smallest sum when we have more than one solution
        if (Math.abs(targetDiff) < Math.abs(smallestDifference)
            || (Math.abs(targetDiff) == Math.abs(smallestDifference) && targetDiff > smallestDifference))
          smallestDifference = targetDiff; // save the closest and the biggest difference  

        if (targetDiff > 0)
          left  ; // we need a triplet with a bigger sum
        else
          right--; // we need a triplet with a smaller sum
      }
    }
    return targetSum - smallestDifference;
  }

  public static void main(String[] args) {
    System.out.println(TripletSumCloseToTarget.searchTriplet(new int[] { -2, 0, 1, 2 }, 2));
    System.out.println(TripletSumCloseToTarget.searchTriplet(new int[] { -3, -1, 1, 2 }, 1));
    System.out.println(TripletSumCloseToTarget.searchTriplet(new int[] { 1, 0, 1, 1 }, 100));
  }
}

The piece of code that I couldn't understand is below :

if (Math.abs(targetDiff) < Math.abs(smallestDifference)
            || (Math.abs(targetDiff) == Math.abs(smallestDifference) && targetDiff > smallestDifference))

More specifically the expression (Math.abs(targetDiff) == Math.abs(smallestDifference) && targetDiff > smallestDifference)). Suppose my previous smallest difference is -2 and in next step my targetDiff comes out to be 2 . Then why I am updating my smallest difference to targetDiff .

For instance my sum of triplets are say - 3,4,5 and my targetSum value is 8. Then the targetDiff comes out to be (5,4,3) and the smallestDifference is 3. That makes sense but in case of equality I couldn't get the logic. Please help.

CodePudding user response：

If two triplets have the same difference from the target it means they either have the same sum, or that one has a positive difference and the other a negative difference from the target with the same absolute value. If this is the case, the triplet with the positive difference (that is larger than the negative difference, by definition) has the smaller sum, and should be picked.

CodePudding user response：

When there are multiple triplets you want to return the one that has the smallest sum, therefore the one that has the largest diff. It's math, consider this:

Let's assume that 

diff1 = targetSum - sum(triplet1)
diff2 = targetSum - sum(triplet2)
abs(diff1) = abs(diff2)

if (sum(triplet1) < sum(triplet2)), then 

-sum(triplet1) > -sum(triplet2), therefore

diff2 < diff1

You want to select triplet1 as it has the smallest sum, which is equivalent to selecting the largest diff (diff1).

By the way, the solution seems inefficient, it has an outer and an inner loop which are very likely to duplicate work across iterations. There has to be a better way (maybe dynamic programming?).

CodePudding user response：

The logics to get the answer is as follows:

initialize with the first sum;

For all new candidate sums

compute the absolute distance to the target;
if smallest than the best distance found so far, keep the new sum;
if equal to the best distance found so far and smaller than the best sum so far, keep the new sum.

That's it.