Question

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

16	3Sum Closest

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

@tag-array

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

Java

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

16 - 3Sum Closest

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions