Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

3Sum closest challenge

Sharing is caring!

Problem statement
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Sample Input

S = [-1, 2, 1, -4]
target = 1

Sample Output

[-1, 2, 1]

Solution

public class ThreeSum {

    private static int[] solve(int[] a, int t) {
        int[] ans = new int[3];

        Arrays.sort(a);
        int n = a.length;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int j = i + 1;
            int k = n - 1;

            while (j < k) {
                int sum = a[i] + a[j] + a[k];
                int diff = Math.abs(sum - t);
                if (diff == 0) {
                    return ans;
                }

                if (diff < min) {
                    min = diff;
                    ans = new int[] { a[i], a[j], a[k] };
                }

                if (sum < t) {
                    // Increment current sum
                    j++;
                } else {
                    // Decrement current sum
                    k--;
                }
            }

        }

        return ans;
    }

    public static void main(String[] args) {
        int[] a = { -1, 2, 1, -4 };
        int t = 1;
        int[] r = solve(a, t);
        System.out.println(r[0] + ", " + r[1] + ", " + r[2]);
    }
}