Sponsored
Sponsored
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.
1var threeSumClosest = function(nums, target) {
2 nums.sort((a, b) => a - b);
3 let closestSum = Infinity;
4 for (let i = 0; i < nums.length - 2; i++) {
5 let left = i + 1,
6 right = nums.length - 1;
7 while (left < right) {
8 const currentSum = nums[i] + nums[left] + nums[right];
9 if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
10 closestSum = currentSum;
11 }
12 if (currentSum < target) {
13 left++;
14 } else if (currentSum > target) {
15 right--;
16 } else {
17 return currentSum;
18 }
19 }
20 }
21 return closestSum;
22};In JavaScript, sorting the array first allows for leveraging pointers to evaluate close sums. Sorting simplifies the direct comparisons needed as we move pointers to shrink differences in sums.
This ensures that all logic for summing and comparison runs efficiently even within a dynamic typing context.
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):
3Although 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.