3Sum Closest

---

3Sum Closest: Given an integer array nums of length n 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 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

---

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

---

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

---

Try this Problem on your own or check similar problems:

1. 3Sum
2. 4Sum

Solution:

Java

public int threeSumClosest(int[] nums, int target) {
    Integer closestSum = null;
    Arrays.sort(nums);

    for(int i = 0; i < nums.length - 2; ++i){
        int j = i + 1, k = nums.length - 1;
        while(j < k){
            int sum = nums[i] + nums[j] + nums[k];

            if(sum == target){
              return sum;
            }else if (closestSum == null || Math.abs(target - closestSum) >  Math.abs(target - sum)){
              closestSum = sum;
            }

            if(sum < target){
              ++j;
            }else{
              --k;
            }
        }
    }

    return closestSum;
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  let closestSum = null;
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; ++i) {
    let j = i + 1;
    let k = nums.length - 1;

    while (j < k) {
      const sum = nums[i] + nums[j] + nums[k];

      if (sum === target) {
        return sum;
      } else if (
        closestSum === null ||
        Math.abs(target - closestSum) > Math.abs(target - sum)
      ) {
        closestSum = sum;
      }

      if (sum < target) {
        ++j;
      } else {
        --k;
      }
    }
  }

  return closestSum;
};

Python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest_sum = None

        for i in range(len(nums) - 2):
            j = i + 1
            k = len(nums) - 1

            while j < k:
                current_sum = nums[i] + nums[j] + nums[k]

                if current_sum == target:
                    return current_sum
                elif closest_sum is None or abs(target - closest_sum) > abs(target - current_sum):
                    closest_sum = current_sum

                if current_sum < target:
                    j += 1
                else:
                    k -= 1

        return closest_sum

C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closestSum = INT_MAX;
        int minDiff = INT_MAX;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size() - 2; ++i) {
            int j = i + 1;
            int k = nums.size() - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                int diff = abs(target - sum);

                if (diff < minDiff) {
                    minDiff = diff;
                    closestSum = sum;
                }

                if (sum < target) {
                    ++j;
                } else {
                    --k;
                }
            }
        }

        return closestSum;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n^2)
• Space Complexity: O(1)

---

Explanation:

We use the same two pointers approach on sorted array as we did in 3Sum only this time we don't have to remove the duplicates, we just have to check if the sum of the current triplet is closer to the target than our previous recorded value and adjust the pointers accordingly. The i only has to iterate to the 3 last element since we have to make space for j and k. We achieve the same time complexity as we did in the regular 3Sum problem.