Given an integer array values of length n and an integer goal, find three integers at distinct indices in values such that their sum is closest to goal. Return the sum of these three integers. Each input is guaranteed to have exactly one solution.
Example 1
Input: values = [4, -2, 7, 1], goal = 5
Output: 5
Explanation: The sum closest to 5 is 5 (4 + 1 + 0 = 5, but 0 is not in the array. The closest is 4 + 7 + (-2) = 9, 4 + 1 + (-2) = 3, 7 + 1 + (-2) = 6. 4 + 1 + 7 = 12. 4 + 1 + (-2) = 3. 7 + 1 + (-2) = 6. The closest is 6.
Example 2
Input: values = [10, -5, 3, 2], goal = 8
Output: 7
Explanation: 10 + 3 + (-5) = 8, 10 + 2 + (-5) = 7, 3 + 2 + (-5) = 0, 10 + 3 + 2 = 15. Closest is 7.
Constraints
Case 1
Input: values = [1, 2, 3, 4], goal = 7
Expected: 7
Case 2
Input: values = [-3, 0, 2, 5], goal = 4
Expected: 4
Case 3
Input: values = [100, -100, 50, 0], goal = 10
Expected: 50
Case 4
Input: values = [5, 5, 5, 5], goal = 16
Expected: 15