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.
1import java.util.Arrays;
2
3class Solution {
4 public int threeSumClosest(int[] nums, int target) {
5 Arrays.sort(nums);
6 int closestSum = Integer.MAX_VALUE;
7 for (int i = 0; i < nums.length - 2; i++) {
8 int left = i + 1, right = nums.length - 1;
9 while (left < right) {
10 int currentSum = nums[i] + nums[left] + nums[right];
11 if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
12 closestSum = currentSum;
13 }
14 if (currentSum < target) {
15 left++;
16 } else if (currentSum > target) {
17 right--;
18 } else {
19 return currentSum;
20 }
21 }
22 }
23 return closestSum;
24 }
25}In Java, we achieve the same method by sorting the input array and iterating with two moving pointers to find sums that approximate the target.
Using the two-pointer technique after fixing one element at a time allows efficient checking of possible sum combinations.
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.