16. 3Sum Closest [O(n2)]
文章目录
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
diffwith a large value. - Sort the input array
nums. Iterate through the array:
- For the current position
i, setlotoi + 1, andhito the last index. While the
lopointer is smaller thanhi:- Set
sumtonums[i] + nums[lo] + nums[hi]. If the absolute difference between
sumandtargetis smaller than the absolute value ofdiff:- Set
difftotarget - sum.
- Set
- If
sumis less thantarget, incrementlo. - Else, decrement
hi.
- Set
- If
diffis 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;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论