Welcome to Subscribe On Youtube

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
  • -104 <= target <= 104

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;
    }
    
    

All Problems

All Solutions