## 3Sum Closest

• Time:O(n^2)
• Space:O(|\texttt{ans}|)

## C++

``````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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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:
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 += 1
else:
r -= 1

return ans
``````