14. 3 Sum Closest

Topic :

arrays

Difficulty :

medium

Problem Link :

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

Constraints:

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

solution

import java.io.*;
import java.util.*;
 class ThreeSumClosest
{
  public static void main(String args[])
  {
   int nums[]={-1,2,1,-4};
   int target=1;
   System.out.println(threeSumClosest(nums,target));
  }
  static int threeSumClosest(int[] nums, int target) 
    {   
        int n=nums.length;
        Arrays.sort(nums);
        // we will consider the first 3 numbers are closest to our target
        int sum=nums[0]+nums[1]+nums[2];
        //3 sum approach
        for(int i=0;i<n-2;i++)
        { 
            int low=i+1;
            int high=n-1;
            
            while(low<high)
            {
                int temp=nums[i]+nums[low]+nums[high];
                
                // if diff between temp and target is less than sum and target
                //then temp can be a possible ans so we update the sum
                if(Math.abs(temp-target) < Math.abs(sum-target) ) 
                sum=temp;
                
                if(temp>target) high--;                  
                
                else if(temp<target) low++;            
                
                else return target;
            }
            
        }
        return sum;
    }
}