Question

Formatted question description: https://leetcode.ca/all/16.html

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⁴ <= target <= 10⁴

Algorithm

The problem requires finding the sum of three numbers closest to a given value, which builds on the previous problem of finding the sum of three numbers that are zero. To solve this problem, we need to ensure that the absolute difference between the current sum of three numbers and the given value is minimal. To achieve this, we define a variable diff to record the absolute value of the difference, and then sort the array to start traversing.

The idea is to determine one number and then slide two pointers, left and right, to find the other two numbers. For each combination of two numbers, we calculate the sum of the three numbers and store the absolute value of the difference between the sum and the given value in a new variable newDiff. We then compare newDiff with diff and update diff and the variable closest if newDiff is smaller than diff.

The process is repeated until we have found the combination of three numbers whose sum is closest to the given value. Here is the code:

Code

public class Three_Sum_Closest {

	public static void main(String[] args) {

        Three_Sum_Closest out = new Three_Sum_Closest();
        Solution s = out.new Solution();

        System.out.println(s.threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
	}

    // time: O(N)
    // space: O(1)
    public class Solution {
        public int threeSumClosest(int[] nums, int target) {
            if (nums.length < 3) {
                return Integer.MIN_VALUE;
            }

            Arrays.sort(nums);

            int closest = Integer.MAX_VALUE;
            int result = Integer.MAX_VALUE;

            // hold one pointer, other two pointer moving
            for (int ancher = 0; ancher < nums.length; ancher++) {

                if (ancher > 0 && nums[ancher] == nums[ancher - 1]) continue;

                int i = ancher + 1;
                int j = nums.length - 1;

                while (i < j) {

                    int sum = nums[ancher] + nums[i] + nums[j];
                    if (sum == target) {
                        return target;

                    } else if (sum < target) {
                        // check if closest
                        if (closest > Math.abs(sum - target)) {
                            closest = Math.abs(sum - target);
                            result = sum;
                        }

                        i++;

                        // @note: same here, possibly updated already, note i-1 or i+1
                        while (i < j && nums[i] == nums[i - 1]) {
                            i++;
                        }

                    } else {
                        // check if closest
                        if (closest > Math.abs(sum - target)) {
                            closest = Math.abs(sum - target);
                            result = sum;
                        }

                        j--;

                        // @note: same here, possibly updated already, note i-1 or i+1
                        while (j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
                            j--;
                        }

                    }
                }
            }

            return result;
        }
    }
}

// OJ: https://leetcode.com/problems/3sum-closest/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int threeSumClosest(vector<int>& A, int target) {
        sort(begin(A), end(A));
        int N = A.size(), ans = A[0] + A[1] + A[2];
        for (int i = 0; i < N - 2; ++i) {
            int L = i + 1, R = N - 1;
            while (L < R) {
                long sum = A[L] + A[R] + A[i];
                if (abs(sum - target) < abs(ans - target)) ans = sum;
                if (sum == target) return target;
                if (sum > target) --R;
                else ++L;
            }
        }
        return ans;
    }
};

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        ans = inf
        for i, v in enumerate(nums):
            j, k = i + 1, n - 1
            while j < k:
                t = v + nums[j] + nums[k]
                if t == target:
                    return t
                if abs(t - target) < abs(ans - target):
                    ans = t
                if t > target:
                    k -= 1
                else:
                    j += 1
        return ans

############

class Solution(object):
  def threeSumClosest(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    nums.sort()
    ans = 0
    diff = float("inf")
    for i in range(0, len(nums)):
      start, end = i + 1, len(nums) - 1
      while start < end:
        sum = nums[i] + nums[start] + nums[end]
        if sum > target:
          if abs(target - sum) < diff:
            diff = abs(target - sum)
            ans = sum
          end -= 1
        else:
          if abs(target - sum) < diff:
            diff = abs(target - sum)
            ans = sum
          start += 1
    return ans

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	ans := 1 << 30
	n := len(nums)
	for i, v := range nums {
		j, k := i+1, n-1
		for j < k {
			t := v + nums[j] + nums[k]
			if t == target {
				return t
			}
			if abs(t-target) < abs(ans-target) {
				ans = t
			}
			if t > target {
				k--
			} else {
				j++
			}
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
    nums.sort((a, b) => a - b);
    let ans = 1 << 30;
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            const t = nums[i] + nums[j] + nums[k];
            if (t == target) {
                return t;
            }
            if (Math.abs(t - target) < Math.abs(ans - target)) {
                ans = t;
            }
            if (t > target) {
                --k;
            } else {
                ++j;
            }
        }
    }
    return ans;
};

function threeSumClosest(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);
    let ans: number = 1 << 30;
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            const t: number = nums[i] + nums[j] + nums[k];
            if (t === target) {
                return t;
            }
            if (Math.abs(t - target) < Math.abs(ans - target)) {
                ans = t;
            }
            if (t > target) {
                --k;
            } else {
                ++j;
            }
        }
    }
    return ans;
}

16 - 3Sum Closest

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions