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