3Sum 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.

This problem is similar to the regular 3Sum problem hopwever this time instread of looking for a triplet of numbers which amount to, we're looking for a set of triplet numbers a + b + c which is as close as possible to target. In other terms we are looking for the minimum absolute value of |(a + b + c) - target|

Approach:

• We create a variable closest which we will use use to keep track of the closest element to the target we encounter so far. We initialize it by assigning it the total of the first 3 elementis in the array.

• We will iterate over the array until length of array - 2. We stopped with two items remaining as we're looking for a triplet set of numbers and at that point, we would have already found any possible combination that would have included these remaining two numbers.

• In the inner loop, while executing the bi-directionnal 2Sum Sweep of the remaining parts of the array we then update the closest variable by comparing the absolute value of the difference of this current Sum combination with what was initially in closest

• We can also break of our search for the closest element if the sum equals the target as that would be the closest value possible to the target.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];
        
        for(int i = 0; i < nums.length - 2; i++){
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(Math.abs(sum - target) < Math.abs(closest - target)){
                    closest = sum;
                    if(sum == target) return sum;
                }
                if(sum > target) k--;
                else j++;
            }
        }
        return closest;
    }
}

Time: O(n2) Space: O(1)Constant