135. Nearest Trio Total
A shop owner has a list of item prices in nums and wants to build a gift box from exactly three different items. The box should cost as close as possible to the budget target.
Choose three entries from three different positions of nums and return the sum of their prices that lies closest to target, meaning the sum whose absolute difference from target is smallest. If two different sums are equally close to target (one below and one above), return the smaller of the two. The array has at least three entries, so a valid choice always exists.
Example 1
- Input:
- nums = [4,-3,9,1,-6], target = 2
- Output:
- 2
- Explanation:
The triple (4,-3,1) sums to 2, exactly the target, so the answer is 2.
Example 2
- Input:
- nums = [10,20,30,5], target = 50
- Output:
- 45
- Explanation:
Possible sums: 10+20+30=60, 10+20+5=35, 10+30+5=45, 20+30+5=55. 45 and 55 are both 5 away from 50, so the smaller, 45, is returned.
Example 3
- Input:
- nums = [-1,-1,-1], target = 10
- Output:
- -3
- Explanation:
There is only one triple, with sum -3.
Constraints
3 ≤ nums.length ≤ 2000
-106 ≤ nums[i] ≤ 106
-3 * 106 ≤ target ≤ 3 * 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(1) extra