# 3Sum closest challenge

**Problem statement**

Given an array of n integers, find three integers in 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**

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

**Sample Output**

1 |
[-1, 2, 1] |

**Solution**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
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]); } } |