3 Sum Closest

​Given an array nums of n integers 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:

 Given array nums = [-1, 2, 1, -4], and target = 1.
 
 The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

First we need to sort the input array and then use 3 pointers to point the current element, the next element, and the last element of the input array. If the sum is less than the target, it means we have to add a larger element so the next element moves to the next. If the sum is greater, it means we have to add a smaller element so the last element moves to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise keep iterating.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        
        int result = nums[0] + nums[1] + nums[2];
        if(nums.length == 3){
            return result;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0 ; i < n ; i++){
            int left = nums[i];
            int r = n-1;
            int m = i+1;
            while( m < r){
                int mid = nums[m];
                int right = nums[r];
                int curValue = (left + mid + right);
                if(curValue == target){
                    return target;
                }else if(curValue < target){
                    m++;
                }else{
                    r--;
                }
                if(Math.abs(target - curValue) < Math.abs(target - result)){
                    result = curValue;
                }
            }
        }
        return result;
    }
}

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s