16.md

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

Thinking process

1. Similar to the 3Sum problem, sort the array first in order to use 2 pointers
2. Keep a global minimum difference, and the closest sum to target so far
3. Iterate through sorted array, call twoSum subroutine each time to complete a full sweep of the rest of the array, update diff and closestSum accordingly
4. Return the closest sum

public int threeSumClosest(int[] nums, int target) {
	int closestSum = 0;
    int diff = Integer.MAX_VALUE;
    Arrays.sort(nums);
    for(int i=0; i < nums.length; i++){
        int low = i + 1;
        int high = nums.length - 1;
        while(low < high){
            int sum = nums[i] + nums[low] + nums[high];
            if(sum == target){
                return sum;
            }else if(sum < target){
                if(target - sum < diff){
                    diff = target - sum;
                    closestSum = sum;
                }
                low++;
            }else{
                if(sum - target < diff){
                    diff = sum - target;
                    closestSum = sum;
                }
                high--;
            }
        }
    }
    return closestSum;
}

Complexity

1. Sorting takes O(nlogn)
2. TwoSum subroutine is called n times, with a complexity of O(n)
3. The overall complexity is O(n²)