LeetCode 16. 3Sum Closest

Description

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Explanation

3Sum Closest is a follow-up question for two sum.

For 3Sum Closest, we are going to find the closet sum to the target. The closet sum could be the target itself or a number close to the target.

1. First, we can sort the array into ascending order.
2. Second, we declare an integer variable called closetSum. That’s the final value we are going to return.
3. Then we can iterate all the numbers in the array. Whenever visiting a number, we should find two numbers in the rest of array which adds the number closet to target. Once iteration finished, we get the result.

Video Tutorial

Java Solution

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return -1;
        }
        
        Arrays.sort(nums);
        
        int closetSum = nums[0] + nums[1] + nums[2];
        
        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(sum - target) < Math.abs(closetSum - target)) {
                    closetSum = sum;
                }
                
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }                        
        }
        
        return closetSum;
    }
}