Three Sum Closest

Given an array of integers and a target value, find three integers in the array such that their sum is closest to the target. It is guaranteed that each input will have exactly one solution. Solve the problem with an algorithm with an expected time complexity of \(O(n^2)\). For example, given the array [2, 3, 5, -2, 8, -1] and target 3, the closest sum is 3.

inputFormat

The input consists of two lines. The first line contains two space-separated integers: \(n\), the number of elements in the array, and \(target\), the target sum. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the sum of the three integers in the array that is closest to the target.

6 3
2 3 5 -2 8 -1

3