- Published on
16. 3Sum Closest
- Authors
- Name
- Loi Tran
- @PrimeTimeTrann
16. 3Sum Closest
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.
Solution
Solve this problem by using three pointers.
Sort input nums
.
Define res
and initialize it's values to any 3 combination of nums. It'll hold our sought value.
Iterate the nums var. This loop's index, i
, is the first pointer.
Within that loop, we initialize the next two pointers, left
and right
.
Loop while l
is smaller than r
.
Sum the values of nums[i] + nums[l] + nums[r] and compare it to target
.
If the sum larger than target
, decrement r
. Otherwise increment l
.
Check if the diff absolute value of cur
minus target
is less than diff of absolute value of res
minus target
.
If so, reassign res
to cur
.
Define response var, sort nums, iterate, return res
Initialize var which holds sought value, res
, which we update while iterating through input nums
.
Iterate the nums
input. This loops incrementor i
will be the first pointer.
Return res
.
// JS syntax is simpler than typed languages
// Input parameters and variables don't
// require type annotation
var threeSumClosest = function(nums, target) {
var res = nums[0] + nums[1] + nums[2];
nums = nums.sort((a, b) => a - b);
for (var i = 0; i < nums.length - 2; i ++) {
}
return res
};
// "nums: number[]" means input param is 'nums', it's type is number[]
function threeSumClosest(nums: number[], target: number): number {
var res = nums[0] + nums[1] + nums[2];
nums = nums.sort((a, b) => a - b);
for (var i = 0; i < nums.length - 2; i ++) {
}
return res
};
// Dart requires typing on return value, the 'int' before threeSumClosest
// It's parameters are also typed. The 'int' before target
class Solution {
int threeSumClosest(List<int> nums, int target) {
var res = nums[0] + nums[1] + nums[2];
nums.sort();
for (var i = 0; i < nums.length - 2; i ++) {
}
return res;
}
}
// Java requires typing of input parameters and variables
// Unlike TS the type comes before the param in function signature.
class Solution {
public int threeSumClosest(int[] nums, int target) {
int res = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
}
return res;
}
}
# In Python3 typing for the function's signature and return value are optional
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
res = nums[0] + nums[len(nums) - 1] + nums[len(nums) - 2]
for i, n in enumerate(nums):
return res
// := allows Go to infer type of 'res'
// from the type of the expression on the right.
// Go also has type annotation on the right of the signature(like TS)
func threeSumClosest(nums []int, target int) int {
res := nums[0] + nums[1] + nums[2]
sort.Ints(nums[:])
for i := 0; i < len(nums) - 2; i++ {
}
return res
}
Use i pointer to initialize next pointer and nest loop
Set l
pointer to i + 1
and r
to the length of nums - 1
In this way we can work our farthest left pointer from left to right and then have the next 2 pointers behave as a sliding window.
Loop while left is smaller than right.
In the loop, sum the values of nums[i] + nums[l] + nums[r]
.
Check this sum, if it matches target
return cur
as we can't get any closer to target.
Otherwise compare is it's greater than target of less and increment/decrement l and r as appropriate.
Remember, the idea here is we want the sum to be 0
.
//
var threeSumClosest = function(nums, target) {
var res = nums[0] + nums[1] + nums[2];
nums = nums.sort((a, b) => a - b);
for (var i = 0; i < nums.length - 2; i ++) {
var l = i + 1
var r = nums.length - 1
while (l < r) {
var cur = nums[i] + nums[l] + nums[r]
if (cur == target) return cur
if (cur > target) {
r -= 1
} else if (cur < target) {
l += 1
}
}
}
return res
};
//
function threeSumClosest(nums: number[], target: number): number {
var res = nums[0] + nums[1] + nums[2];
nums = nums.sort((a, b) => a - b);
for (var i = 0; i < nums.length - 2; i ++) {
var l = i + 1
var r = nums.length - 1
while (l < r) {
var cur = nums[i] + nums[l] + nums[r]
if (cur == target) return cur
if (cur > target) {
r -= 1
} else if (cur < target) {
l += 1
}
}
}
return res
};
//
class Solution {
int threeSumClosest(List<int> nums, int target) {
var res = nums[0] + nums[1] + nums[2];
nums.sort();
for(var i = 0; i < nums.length - 2; i ++) {
var l = i + 1;
var r = nums.length - 1;
while (l < r) {
var cur = nums[i] + nums[l] + nums[r];
if (cur == target) return cur;
if (cur > target) {
r -= 1;
} else if (cur < target) {
l += 1;
}
}
}
return res;
}
}
//
class Solution {
public int threeSumClosest(int[] nums, int target) {
int res = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
int cur = nums[i] + nums[l] + nums[r];
if (cur > target) {
r -= 1;
} else {
l += 1;
}
}
}
return res;
}
}
#
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
res = nums[0] + nums[len(nums) - 1] + nums[len(nums) - 2]
for i, n in enumerate(nums):
l = i + 1
r = len(nums) - 1
while l < r:
curSum = nums[i] + nums[l] + nums[r]
if curSum == target:
return curSum
if curSum > target:
r -= 1
else:
l += 1
return res
//
func threeSumClosest(nums []int, target int) int {
res := nums[0] + nums[1] + nums[2]
sort.Ints(nums[:])
for i := 0; i < len(nums) - 2; i++ {
l := i + 1
r := len(nums) - 1
for l < r {
cur := nums[i] + nums[l] + nums[r]
if cur > target {
r -= 1
} else {
l += 1
}
}
}
return res
}
Check the difference between cur and res
Compare the absolute different of cur - target
and res - target
to find which is closet to zero. If cur
is smaller then reassign res
to cur
.
Use math's absolute in case the value becomes negative.
And finally optimize the outer loop comparing if the previous i
is the same as this i
. If so, continue to the next iteration.
// Math.abs is helpful here.
var threeSumClosest = function(nums, target) {
var res = nums[0] + nums[1] + nums[2];
nums = nums.sort((a, b) => a - b);
for (var i = 0; i < nums.length - 2; i ++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue
}
var l = i + 1
var r = nums.length - 1
while (l < r) {
var cur = nums[i] + nums[l] + nums[r]
if (cur == target) return cur
if (cur > target) {
r -= 1
} else if (cur < target) {
l += 1
}
if (Math.abs(cur - target) < Math.abs(res - target)) {
res = cur
}
}
}
return res
};
//
function threeSumClosest(nums: number[], target: number): number {
var res = nums[0] + nums[1] + nums[2];
nums = nums.sort((a, b) => a - b);
for (var i = 0; i < nums.length - 2; i ++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue
}
var l = i + 1
var r = nums.length - 1
while (l < r) {
var cur = nums[i] + nums[l] + nums[r]
if (cur == target) return cur
if (cur > target) {
r -= 1
} else if (cur < target) {
l += 1
}
if (Math.abs(cur - target) < Math.abs(res - target)) {
res = cur
}
}
}
return res
};
//
class Solution {
int threeSumClosest(List<int> nums, int target) {
var res = nums[0] + nums[1] + nums[2];
nums.sort();
for (var i = 0; i < nums.length - 2; i ++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
var l = i + 1;
var r = nums.length - 1;
while (l < r) {
var cur = nums[i] + nums[l] + nums[r];
if (cur == target) return cur;
if (cur > target) {
r -= 1;
} else if (cur < target) {
l += 1;
}
if ((cur - target).abs() < (res - target).abs()) {
res = cur;
}
}
}
return res;
}
}
//
class Solution {
public int threeSumClosest(int[] nums, int target) {
int res = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
int cur = nums[i] + nums[l] + nums[r];
if (cur > target) {
r -= 1;
} else {
l += 1;
}
if (Math.abs(cur - target) < Math.abs(res - target)) {
res = cur;
}
}
}
return res;
}
}
# Python has abs as well.
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
res = nums[0] + nums[len(nums) - 1] + nums[len(nums) - 2]
for i, n in enumerate(nums):
if (i > 0) and nums[i - 1] == nums[i]:
continue
l = i + 1
r = len(nums) - 1
while l < r:
curSum = nums[i] + nums[l] + nums[r]
if curSum == target:
return curSum
if curSum > target:
r -= 1
else:
l += 1
if abs(curSum - target) < abs(res - target):
res = curSum
return res
// Go doesn't have built in support for mathematical abs
// so we have to implement it ourselves.
func absInt(x int) int {
return absDiffInt(x, 0)
}
func absDiffInt(x, y int) int {
if x < y {
return y - x
}
return x - y
}
func threeSumClosest(nums []int, target int) int {
res := nums[0] + nums[1] + nums[2]
sort.Ints(nums[:])
for i := 0; i < len(nums) - 2; i++ {
if i > 0 && nums[i] == nums[i - 1] {
continue
}
l := i + 1
r := len(nums) - 1
for l < r {
cur := nums[i] + nums[l] + nums[r]
if cur > target {
r -= 1
} else {
l += 1
}
if absInt(cur - target) < absInt(res - target) {
res = cur
}
}
}
return res
}
Questions? Concerns?
Please comment a better solution if you have one.