Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1 Output: 0 Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-104 <= target <= 104To solve 3Sum Closest, the key idea is to reduce the search space efficiently instead of checking every possible triplet. A common strategy is to sort the array first, which allows the use of the two pointers technique. After sorting, iterate through the array and treat each element as the first number of the triplet. For the remaining two numbers, place one pointer at the start and another at the end of the remaining subarray.
By comparing the current sum with the target, you can adjust the pointers to move closer to the desired value. Keep track of the closest sum encountered during the traversal. Sorting enables predictable pointer movements and avoids unnecessary combinations.
This approach significantly improves performance compared to brute force. While a naive method would check all triplets in O(n^3), the optimized approach reduces the time complexity to O(n^2) with minimal additional space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check all triplets) | O(n^3) | O(1) |
| Sorting + Two Pointers | O(n^2) | O(1) |
NeetCode
This approach involves first sorting the array, and then using a two-pointer technique. For each element, we treat it as the first element of a potential triplet and place two pointers at the ends of the remaining subarray. We then move these pointers inward, calculating the sum at each position and comparing it to the target. By maintaining the sum closest to the target found so far, we can track the desired result.
Time Complexity: O(n^2) as the sorting takes O(n log n) and the two-pointer scanning for each element takes O(n).
Space Complexity: O(1) as no additional space is used apart from input handling.
1def threeSumClosest(nums, target):
2 nums.sort()
3 closest_sum = float('inf')
4 for i in range(len(nums) We begin by sorting the array to simplify the evaluation of possible sums using a two-pointer technique.
We iterate over the array with a fixed element and set two pointers: one initial (left) and the other one at the end of the array (right). We attempt to bring their sum closer to the target by moving these pointers inward based on the evaluation.
Throughout, we track the closest sum to the target found so far and update it whenever we find a sum with a smaller absolute difference from the target.
An alternative approach uses a hashmap to store results of sums previously obtained, attempting to minimize recalculation. This helps when you want quick hash-map based lookups. Although less commonly optimal for this problem, its concept is crucial to explore for diverse method understanding. However, the typical 3Sum problem resolved via hashmap cannot be translated well into this one because storing potential sums doesn't help reduce the complexity below O(n^2) as comparisons per pair are required.
Time Complexity: Still O(n^2) due to needed dual-pointer validation.
Space Complexity: Could exceed simplicity due to extra dictionary operations, no pragmatic benefit here.
1# Hashmap approach is commonly less efficient here but holds educational value.
2def threeSumClosest(nums, target):
3Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting helps organize the numbers so pointer movements become predictable. When the current sum is too small or too large, you can move the left or right pointer accordingly to approach the target efficiently.
Yes, variations of 3Sum problems are commonly asked in technical interviews at companies like Amazon, Google, and Meta. They test understanding of sorting, two pointers, and optimization from brute force approaches.
The optimal approach is to first sort the array and then use the two pointers technique. Fix one element and move two pointers across the remaining array to adjust the sum toward the target. This reduces the complexity to O(n^2).
The problem primarily relies on arrays along with sorting and pointer manipulation. No complex data structure is required, but sorting the array enables efficient traversal with two pointers.
Although attempting to use a hashmap for distinct sums can be slower, the number of cases where recalculation avoided helps understand alternative paradigms for lookup or reference use as applied to sum and distance analysis. Since pairing three amounts prevalently defects hashmap efficiency virtue, this becomes an academic exercise given the nature of two-pointer solutions being inherently simpler.