# 16. 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.

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

# Solution

Approach 1: Sorting and then for each number, do 2-sum for the rest of numbers.

# Code (Python)

Approach 1:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if not nums or len(nums) < 3:
            return float('inf')
        nums.sort()
        closest = nums[0] + nums[1] + nums[2]
        for lowest in range(len(nums) - 2):
            l, r = lowest + 1, len(nums) - 1
            while l < r:
                sum_of_3 = nums[lowest] + nums[l] + nums[r]
                if abs(closest - target) > abs(sum_of_3 - target):
                    closest = sum_of_3
                if sum_of_3 < target:
                    l += 1
                elif sum_of_3 > target:
                    r -= 1
                else:
                    return target
        return closest

# Code (C++)

Approach 1:

class Solution {
private:
    int twoSumClosest(vector<int>& nums, int head, int tail, int target) {
        int closestSum = nums[head] + nums[tail];
        int i = head;
        int j = tail;
        while (i < j)
        {
            int sum = nums[i] + nums[j];
            if (abs(sum - target) < abs(closestSum - target))
                closestSum = sum;
            if (sum < target)
                i++;
            else
                j--;
        }
        return closestSum;
    }
public:
    int threeSumClosest(vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());
        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i <= nums.size() - 3; ++i)
        {
            int sum = nums[i] + twoSumClosest(nums, i + 1, nums.size() - 1, target - nums[i]);
            if (abs(sum - target) < abs(closestSum - target))
                closestSum = sum;
        }
        return closestSum;
    }
};