# 3Sum Closest LeetCode Solution | C++, Java, Python | Easy Approach

Share:

3Sum Closest | Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

Constraints:

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Time: O(n*n)
Space: O(|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 String intToRoman(int num) {
final int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
final String[] symbols = {"M",  "CM", "D",  "CD", "C",  "XC", "L",
"XL", "X",  "IX", "V",  "IV", "I"};
StringBuilder sb = new StringBuilder();

for (int i = 0; i < values.length; ++i) {
if (num == 0)
break;
while (num >= values[i]) {
num -= values[i];
sb.append(symbols[i]);
}
}

return sb.toString();
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

#### Watch Tutorial

Checkout more Solutions here