Triplet Nearest Sum

Medium

You are given an integer array nums containing n elements and an integer target value. Your task is to identify three distinct elements from the array (elements at different indices) such that their sum is as close as possible to the target . Return the sum of the three selected integers . You may assume that each input will have exactly one unique solution — meaning there will always be precisely one triplet whose sum is closest to the target. Key Observations The three elements must come from different positions in the array (i.e., you cannot use the same element twice even if it appears multiple times). "Closest" means the absolute difference between the triplet sum and the target is minimized. When the exact target sum is achievable with three elements, that sum should be returned. The array may contain negative numbers, zero, and positive numbers.

Example 1

Input

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

Output

Explanation

The triplet that produces the sum closest to the target is (-1, 2, 1). Their sum is -1 + 2 + 1 = 2, which is only 1 unit away from the target value of 1. No other triplet gets closer to the target.

Example 2

Input

nums = [0, 0, 0]
target = 1

Output

Explanation

The only possible triplet consists of all three zeros: 0 + 0 + 0 = 0. Although the target is 1, the closest achievable sum is 0 since that is the only triplet available.

Example 3

Input

nums = [1, 2, 3, 4, 5]
target = 9

Output

Explanation

Multiple triplets are possible here: (1,2,3)=6, (1,2,4)=7, (1,2,5)=8, (1,3,4)=8, (1,3,5)=9, (1,4,5)=10, (2,3,4)=9, (2,3,5)=10, (2,4,5)=11, (3,4,5)=12. The triplets (1,3,5) and (2,3,4) both sum to exactly 9, which equals the target. Since this is the closest possible (difference of 0), we return 9.

Constraints

3 ≤ nums.length ≤ 500
-1000 ≤ nums[i] ≤ 1000
-10⁴ ≤ target ≤ 10⁴
Exactly one unique solution exists for each input.