Solution for LeetCode 3sum Closet, with Cpp/Java/Python

LeetCode Problem https://leetcode.com/problems/3sum-closest/

Given an array nums of n integers 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:

`Given array nums = [-1, 2, 1, -4], and target = 1.` The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Explaination Naive solution will enumerate the array with three loop:

`diff = max_integer` for(a = 0, a < arr.size(), a++) for(b = a+1, b < arr.size() - 1, b++) for(c = b+1, c < arr.size() - 1, c++) if(abs(target - (a+b+c) < diff) update diff ...

The time complexity of course should be $O(N^3)$.

Actually this problem is almost same with previous LeetCode: 3Sum , except we need to find the closet sum of three elements.

Sort the array and use the method of fixing head or tail index, according to current sum, the complexity will be $O(N^2)$.

C++ class Solution {public : int threeSumClosest (vector <int > &num, int target) { int diff = INT_MAX; int ans = 0 ; sort(num.begin(), num.end()); if (num.size() < 3 ) return ans; for (size_t first = 0 ; first < num.size(); first++) { int head = first + 1 ; int tail = num.size() - 1 ; while (head < tail) { int sum3 = num[head] + num[tail] + num[first]; int d = abs (sum3 - target); if (d == 0 ) return target; if (d < diff) { diff = d; ans = sum3; } if (sum3 > target) tail--; if (sum3 < target) head++; } while (first < num.size()-1 && num[first+1 ] == num[first]) first++; } return ans; } };

Java class Solution { public int threeSumClosest (int [] nums, int target) { Arrays.sort(nums); int diff = Integer.MAX_VALUE; int ans = 0 ; if (nums.length < 3 ) return ans; for (int first = 0 ; first < nums.length; first++) { int head = first + 1 ; int tail = nums.length - 1 ; while (head < tail) { int sum3 = nums[head] + nums[tail] + nums[first]; int d = Math.abs(sum3 - target); if (d == 0 ) return target; if (d < diff) { diff = d; ans = sum3; } if (sum3 > target) tail--; if (sum3 < target) head++; } while (first < nums.length-1 && nums[first+1 ] == nums[first]) first++; } return ans; } }

Python class Solution : def threeSumClosest (self, nums: List[int ], target: int ) -> int: nums.sort() ans = sum (nums[:3 ]) for i in range (len (nums)-2 ): k = len (nums)-1 j = i + 1 while j < k: close_sum = nums[i] + nums[j] + nums[k] if close_sum == target: return close_sum if abs (close_sum - target) < abs (ans - target): ans = close_sum if close_sum < target: j += 1 elif close_sum > target: k -= 1 else : break return ans

Preparing for an interview? Check out this!