16. 3Sum Closest(Solution || Leetcode medium || Java)

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

SOLUTION:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
//First we need to sort the array as without sorting it will get
//too complex
        Arrays.sort(nums);
        
//initialise a valribale to store the minimum difference
        int diff = Integer.MAX_VALUE;
//initialise variable to store the sum of the three elements
        int ans = 0;
        
//We will use pointers for this
        for(int i = 0; i < nums.length - 2; i++){

           //First pointer
            int low = i+1;

           //Second pointer
            int high = nums.length - 1;

//Let our first number be nums[i], now we are going to search for
//remanining two numbers whose sum will give us the minimum difference
//to the target
            int sum = target - nums[i];
            
            while(low < high){

//if at any point two elements addition is equal to sum 
//then it means by adding the three numbers that are
//nums[i]+nums[low]+nums[high] we will get our target
//hence the difference between sum and target is 0
//so return target
                if(nums[high] + nums[low] == sum){
                    return target;
                }
       else if(nums[high] + nums[low] > sum){
 diff = Math.min(diff,Math.abs(target - (nums[i] + nums[low] + nums[high])));
     if(diff == Math.abs(target - (nums[i] + nums[low] + nums[high]))){
            ans = nums[i] + nums[low] + nums[high];
                    }
                    high--;
                }
        else{
 diff= Math.min(diff,Math.abs(target - (nums[i] + nums[low] + nums[high])));
      if(diff == Math.abs(target - (nums[i] + nums[low] + nums[high]))){
            ans = nums[i] + nums[low] + nums[high];
                    }
                    low++;
                }
            }
        }
        
        return ans;
    }
}

Runtime: 17 ms, faster than 94.87% of Java online submissions for 3Sum Closest.

Memory Usage: 41.5 MB, less than 99.85% of Java online submissions for 3Sum Closest.

Thank you for reading. If you have any queries then, please let me know in the comment section. I will surely be responsive toward it.