607. The Triple Nearest a Target
Given n integers and a target, choose three of them, by position, and print the sum that
comes closest to the target.
If two achievable sums are equally close, print the SMALLER one.
-1 2 1 -4, target 1 -> 2 from -1 + 2 + 1
10 20 30, target 5 -> 60 the only triple there is
## The change from 606
Same sort, same fixed outer element, same converging inner pair. The only differences are that nothing is being matched exactly, and that a best-so-far is carried along.
That is worth noticing: once the sweep is understood as "the sum tells you which end to move", it adapts to exact hits, nearest hits and counts without changing shape.
## The sweep
sort
best = the first sum seen
for i from 0 to n-3:
lo = i+1, hi = n-1
while lo < hi:
s = a[i] + a[lo] + a[hi]
update best with s
s < target -> lo += 1
s > target -> hi -= 1
s == target -> stop, nothing can be closer
## Why moving toward the target is right
If s < target, the only way to get a larger sum with this i and this hi is a larger
a[lo], so lo advances. Every pair using the CURRENT lo with a smaller hi gives a sum no
larger than s, and therefore no closer from below, so those are safely skipped.
An exact hit ends the search, because nothing has distance less than zero.
## The tie-break, and why it must be stated
A target exactly between two achievable sums is genuinely ambiguous. On 1 2 4 5 the
achievable sums are 7 8 10 11, so a target of 9 sits one away from both 8 and 10. On
0 0 1 3 the sums are 1 3 4, and a target of 2 is one away from both 1 and 3.
Without a stated rule, two correct programs disagree and neither is wrong. The statement fixes
it: the SMALLER sum wins. Compare with abs(s - target) < abs(best - target), and on equality
take s < best.
Any problem whose answer is a chosen value rather than a count needs this kind of rule, and the absence of one is a bug in the problem, not in the solution.
## Boundaries
With exactly three values there is one triple and it is the answer, however far off.
Sums of three values near 10^9 reach 3 * 10^9, and s - target reaches 4 * 10^9. Use 64
bits for both.
## Cost
Time O(n^2). Space O(1) beyond the input.
Constraints - `3 ≤ n ≤ 3000` - `-10^9 ≤ each value ≤ 10^9` - `-10^9 ≤ target ≤ 10^9`
Input
The first line contains two integers n and target.
The second line contains n integers.
Output
Print one integer, the achievable three-value sum closest to the target, the smaller one on a tie.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.