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
3Sum Closest Solutions
✅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