LeetCode Solutions
16. 3Sum Closest
Time: $O(n^2)$ Space: $O(|\texttt{ans}|)$
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int ans = nums[0] + nums[1] + nums[2];
sort(begin(nums), end(nums));
for (int i = 0; i + 2 < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first num in the triplet,
// and search the remaining nums in [i + 1, n - 1]
int l = i + 1;
int r = nums.size() - 1;
while (l < r) {
const int sum = nums[i] + nums[l] + nums[r];
if (sum == target)
return sum;
if (abs(sum - target) < abs(ans - target))
ans = sum;
if (sum < target)
++l;
else
--r;
}
}
return ans;
}
};
class Solution {
public int threeSumClosest(int[] nums, int target) {
int ans = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i + 2 < nums.length; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
// Choose nums[i] as the first num in the triplet,
// and search the remaining nums in [i + 1, n - 1]
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
final int sum = nums[i] + nums[l] + nums[r];
if (sum == target)
return sum;
if (Math.abs(sum - target) < Math.abs(ans - target))
ans = sum;
if (sum < target)
++l;
else
--r;
}
}
return ans;
}
}
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
ans = nums[0] + nums[1] + nums[2]
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
l = i + 1
r = len(nums) - 1
while l < r:
summ = nums[i] + nums[l] + nums[r]
if summ == target:
return summ
if abs(summ - target) < abs(ans - target):
ans = summ
if summ < target:
l += 1
else:
r -= 1
return ans