Last updated on February 2nd, 2025 at 06:53 am
Here, we see the 3Sum Closest LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Two-Pointers
Companies
Bloomberg
Level of Question
Medium
3Sum Closest LeetCode Solution
Table of Contents
1. Problem Statement
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
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
2. Coding Pattern Used in Solution
The code uses the Two Pointers pattern. This pattern is commonly used when dealing with sorted arrays or lists, where two pointers are used to traverse the array from different ends (or positions) to find a solution. In this case, the two pointers (j and k in C++/Java, left and right in JavaScript/Python) are used to find the closest sum of three numbers to the target.
3. Code Implementation in Different Languages
3.1 3Sum Closest C++
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int n=nums.size();
int sum=nums[0]+nums[1]+nums[2];
for(int i=0;i<n-2;i++){
int j=i+1;
int k=n-1;
while(j<k){
int temp=nums[i]+nums[j]+nums[k];
if(abs(temp-target) < abs(sum-target) ) sum=temp;
if(temp>target){
k--;
} else if(temp<target){
j++;
}else return target;
}
return sum;
}
};
3.2 3Sum Closest Java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closestSum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (Math.abs(target - sum) < Math.abs(target - closestSum)) {
closestSum = sum;
}
if (sum < target) {
j++;
} else {
k--;
}
}
}
return closestSum;
}
}
3.3 3Sum Closest JavaScript
var threeSumClosest = function(nums, target) {
nums.sort((a, b) => a - b);
let n = nums.length;
let closest_sum = nums[0] + nums[1] + nums[2];
for (let i = 0; i < n - 2; i++) {
let left = i + 1, right = n - 1;
while (left < right) {
let sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return sum;
} else if (sum < target) {
left++;
} else {
right--;
}
if (Math.abs(sum - target) < Math.abs(closest_sum - target)) {
closest_sum = sum;
}
}
}
return closest_sum;
};
3.4 3Sum Closest Python
class Solution(object):
def threeSumClosest(self, nums, target):
nums.sort()
n = len(nums)
closest_sum = nums[0] + nums[1] + nums[2]
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum == target:
return sum
elif sum < target:
left += 1
else:
right -= 1
if abs(sum - target) < abs(closest_sum - target):
closest_sum = sum
return closest_sum
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(log n) |
| Java | O(n²) | O(log n) |
| JavaScript | O(n²) | O(log n) |
| Python | O(n²) | O(log n) |
- The Two Pointers pattern is efficient for problems involving sorted arrays and finding pairs or triplets that satisfy a condition.
- The algorithm is optimal for this problem, as it avoids brute-forcing all possible triplets (which would take O(n³) time). Instead, it reduces the complexity to O(n²) by leveraging the sorted array and two-pointer traversal.