Three Sum Closest
Medium · Two Pointers · Array · Two Pointers · Sorting
Problem
Given an integer array nums and an integer target, choose three numbers from three different positions whose sum is as close as possible to target, and return that sum.
Every input has exactly one closest sum: two different sums are never equally far from target.
Examples
Input: nums = [-3,2,5,8], target = 6 Output: 7
The possible sums are 4, 7, 10 and 15. 7 is 1 away from 6; nothing is closer.
Input: nums = [1,1,1], target = -10 Output: 3
Only one triplet exists, so its sum is the answer however far it is.
Input: nums = [-4,-1,0,3,9], target = 2 Output: 2
-1 + 0 + 3 hits the target exactly.
Constraints
- 3 <= len(nums) <= 500
- -1000 <= nums[i] <= 1000
- -10^4 <= target <= 10^4
- Exactly one sum is closest to target
Approaches
- Every triplet — time O(n³), space O(1)
Follow-up
What if you must return the closest sum of four numbers? Fix two numbers with two loops and close the last two with pointers: O(n³). In general k numbers cost O(n^(k-1)).
Related problems
Start free on Cariara · Coding problems · System design studio
