3Sum Closest – Leetcode Solution

In this post, we are going to solve the 16. 3Sum Closest problem of Leetcode. This problem 16. 3Sum Closest is a Leetcode medium level problem. Let’s see code, 16. 3Sum Closest.

Problem

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).

Constraints

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

Now, let’s see the code of 16. 3Sum Closest – Leetcode Solution.

3Sum Closest – Leetcode Solution

16. 3Sum Closest – Solution in Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int diff = Integer.MAX_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum  = nums[i] + nums[left] + nums[right];
                
                if (Math.abs(target - sum) < Math.abs(diff)) {
                    diff = target - sum;
                }
                
                if (sum > target) {
                    right--;
                }
                else {
                    left++;
                }
            }
        }
        return (target-diff);
    }
}

16. 3Sum Closest – Solution in C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n-2; ++i) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum3 = nums[i] + nums[l] + nums[r];
                if (abs(ans - target) > abs(sum3 - target)) 
                    ans = sum3;
                if (sum3 == target) break;
                if (sum3 > target)
                    --r; 
                else
                    ++l; 
            }
        }
        return ans;
    }
};

16. 3Sum Closest – Solution in Python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        ans = nums[0] + nums[1] + nums[2]
        for i in range(n-2):
            l, r = i + 1, n - 1
            while l < r:
                sum3 = nums[i] + nums[l] + nums[r]
                if abs(ans - target) > abs(sum3 - target):
                    ans = sum3
                if sum3 == target: return target
                if sum3 > target:
                    r -= 1  
                else:
                    l += 1  
        return ans

Note: This problem 16. 3Sum Closest is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *