3Sum Closest - Java Solution

1. Introduction

This blog post is focused on solving a classic problem in array processing: finding a triplet whose sum is closest to a given target value. This problem is a variant of the two-pointer technique, often used in solving array-related problems.

Problem

Given an array of unsorted integers a and a target value, the goal is to find a triplet in the array whose sum is closest to the target value and return the sum of the triplet.

Example 1:

Input: a[] = [-2, -4, 6, 3, 7], target = 2

Output: 1

Explanation: The triplet with a sum closest to the target is [-2, -4, 7], and its sum is 1.

Example 2:

Input: a[] = [10, 2, 30, 49, 8], target = 50

Output: 48

Explanation: The triplet with a sum closest to the target is [10, 30, 8], and its sum is 48.

Example 3:

Input: a[] = [1, 0, 5, 0, 3], target = 100

Output: 9

Explanation: The triplet with a sum closest to the target is [1, 5, 3], and its sum is 9.

2. Solution Steps

1. Sort the array.

2. Initialize a variable to store the closest sum.

3. Iterate through the array, using each element as a fixed point for the triplet.

4. Use two pointers to find the other two elements of the triplet.

5. Update the closest sum if the current triplet sum is closer to the target.

6. Adjust the pointers based on the comparison between the triplet sum and the target.

7. Return the closest sum.

3. Code Program

import java.util.Arrays;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a1 = {-2, -4, 6, 3, 7};
        int[] a2 = {10, 2, 30, 49, 8};
        int[] a3 = {1, 0, 5, 0, 3};

        System.out.println("Closest sum to target: " + findClosestSum(a1, 2));
        System.out.println("Closest sum to target: " + findClosestSum(a2, 50));
        System.out.println("Closest sum to target: " + findClosestSum(a3, 100));
    }

    // Method to find the triplet sum closest to the target
    public static int findClosestSum(int[] a, int target) {
        Arrays.sort(a);
        int closestSum = Integer.MAX_VALUE / 2; // Using Integer.MAX_VALUE/2 to avoid overflow

        for (int i = 0; i < a.length - 2; i++) {
            int left = i + 1, right = a.length - 1;
            while (left < right) {
                int currentSum = a[i] + a[left] + a[right];

                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }

                if (currentSum > target) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return closestSum;
    }
}

Output:

Closest sum to target: 1
Closest sum to target: 48
Closest sum to target: 9

Explanation:

The findClosestSum method sorts the array and then iterates over it, using a fixed point and two pointers to find the closest sum to the target. 

For example, in the array [-2, -4, 6, 3, 7] with a target of 2, it identifies the closest sum as 1, achieved by the triplet [-2, -4, 7]. 

The method efficiently finds the closest sum for each example, demonstrating the effectiveness of the two-pointer technique.