共计 1569 个字符,预计需要花费 4 分钟才能阅读完成。
This problem is a variation of 3Sum. The main difference is that the sum of a triplet is not necessarily equal to the target. Instead, the sum is in some relation with the target, which is closest to the target for this problem. In that sense, this problem shares similarities with 3Sum Smaller.
Before jumping in, let’s check solutions for the similar problems:
- 3Sum fixes one number and uses either the two pointers pattern or a hash set to find complementary pairs. Thus, the time complexity is \mathcal{O}(n^2)O(n2).
- 3Sum Smaller, similarly to 3Sum, uses the two pointers pattern to enumerate smaller pairs. Note that we cannot use a hash set here because we do not have a specific value to look up.
For the same reason as for 3Sum Smaller, we cannot use a hash set approach here. So, we will focus on the two pointers pattern and shoot for \mathcal{O}(n^2)O(n2) time complexity as the best conceivable runtime (BCR).
Algorithm
- Initialize the minimum difference
diff
with a large value. - Sort the input array
nums
. -
Iterate through the array:
- For the current position
i
, setlo
toi + 1
, andhi
to the last index. -
While the
lo
pointer is smaller thanhi
:- Set
sum
tonums[i] + nums[lo] + nums[hi]
. -
If the absolute difference between
sum
andtarget
is smaller than the absolute value ofdiff
:- Set
diff
totarget - sum
.
- Set
- If
sum
is less thantarget
, incrementlo
. - Else, decrement
hi
.
- Set
- If
diff
is zero, break from the loop.
- For the current position
- Return the value of the closest triplet, which is
target - diff
.
class Solution {public int threeSumClosest(int[] nums, int target) {
int diff = Integer.MAX_VALUE;
Arrays.sort(nums);
for(int i = 0; i < nums.length -2; i++) {
int lo = i+1;
int hi = nums.length - 1;
while(lo < hi) {int sum = nums[i] + nums[lo] + nums[hi];
if (Math.abs(target - sum) < Math.abs(diff)) {diff = target - sum;}
if(sum < target) {lo++;}
else if(sum > target) {hi--;}
else {break;}
}
}
return target - diff;
}
}