Welcome to Subscribe On Youtube
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