3Sum Closest
Medium · Two Pointers · Explanation and code example
Sorting and Two Pointers
How it works
After sorting, fix the first number and search the remaining suffix with two pointers. A sum below the target needs a larger left value; a sum above it needs a smaller right value. Track the closest sum encountered, returning immediately on an exact match.
Steps
- Sort the array and initialize a valid three-number sum.
- For each first index, scan the suffix from both ends.
- Update the closest sum and move the appropriate pointer.
Complexity
- Time: O(n²).
- Space: Python O(n) worst-case sorting workspace; C++ O(log n) sorting stack.
Things to watch for
- Return the sum, rather than the distance to the target.
- Each triplet must use three different indices.
- Sorting changes the input order.
Python code example
class Solution:
def threeSumClosest(self, nums: list[int], target: int) -> int:
ans = nums[0] + nums[1] + nums[2]
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
# Choose nums[i] as the first number in the triplet, then search the
# remaining numbers in [i + 1, n - 1].
l = i + 1
r = len(nums) - 1
while l < r:
summ = nums[i] + nums[l] + nums[r]
if summ == target:
return summ
if abs(summ - target) < abs(ans - target):
ans = summ
if summ < target:
l += 1
else:
r -= 1
return ans
C++ code example
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int ans = nums[0] + nums[1] + nums[2];
ranges::sort(nums);
for (int i = 0; i + 2 < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first number in the triplet, then search the
// remaining numbers in [i + 1, n - 1].
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
const int sum = nums[i] + nums[l] + nums[r];
if (sum == target)
return sum;
if (abs(sum - target) < abs(ans - target))
ans = sum;
if (sum < target)
++l;
else
--r;
}
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.