Triple Sum Nearest the Target

Medium

You are given an integer array values and an integer aim. Choose three elements at different indices so that their sum is as close to aim as possible, and return that sum. The closest sum is guaranteed to be unique: there are never two different sums that are equally far from aim and both better than every other.

Example 1

values=[4, -6, 2, 9], aim=3 → 5

The possible triple sums are 0, 7, 5 and 15. The closest to 3 is 5 = -6 + 2 + 9, which is 2 away; 0 is 3 away.

Example 2

values=[1, 1, 1, 1], aim=-50 → 3

Every triple adds up to 3, so the answer is 3 no matter how far away the target is.

Example 3

values=[-3, 0, 5, 8, 2], aim=10 → 10

0 + 2 + 8 = 10 hits the target exactly.

Constraints

3 ≤ len(values) ≤ 1000
-1000 ≤ values[i] ≤ 1000
-10⁴ ≤ aim ≤ 10⁴
The triple sum closest to aim is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Sorting

Similar problems

Zero-Sum Triples Medium Four Numbers to a Target Medium Flags in Three Colors Medium Studios for Recording Sessions Medium Triples Under a Limit Medium

Input

values=[4, -6, 2, 9], aim=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.