16. 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).
Solution
(1) Java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
long rst = Integer.MAX_VALUE;
for (int i = 0; i < nums.length-2; i++) {
if (i != 0 && nums[i] == nums[i-1]) {
continue;
}
int num1 = nums[i];
int left = i+1;
int right = nums.length-1;
while (left < right) {
int sum = num1+nums[left]+nums[right];
if (sum == target) {
return sum;
}
rst = Math.abs(target-sum) < Math.abs(target-rst) ? sum : rst;
if (sum < target) {
while (left < right && nums[left] == nums[left+1]) {
left++;
}
left++;
} else {
while (left < right && nums[right] == nums[right-1]) {
right--;
}
right--;
}
}
}
return (int)rst;
}
}
(2) Python
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
rst = nums[0]+nums[1]+nums[2]
for i in range(len(nums)-2):
left = i+1
right = len(nums)-1
while left < right:
sum = nums[i]+nums[left]+nums[right]
if sum == target:
return sum
if abs(target-sum) < abs(target-rst):
rst = sum
if sum < target:
left += 1
else:
right -= 1
return rst
(3) Scala
object Solution {
def threeSumClosest(nums: Array[Int], target: Int): Int = {
nums.length match {
case 3 => return nums.sum
case _ => {
scala.util.Sorting.quickSort(nums)
var rst = nums(0)+nums(1)+nums(2)
for (i <- 0 until nums.length-2) {
if (i == 0 || nums(i) != nums(i-1)) {
var left = i+1
var right = nums.length-1
while (left < right) {
var sum = nums(i)+nums(left)+nums(right)
if (sum == target) {
return sum
} else {
rst = if (math.abs(target-sum) < math.abs(target-rst)) sum else rst
if (sum < target) {
while (left < right && nums(left) == nums(left+1)) {
left += 1
}
left += 1
} else {
while (left < right && nums(right) == nums(right-1)) {
right -= 1
}
right -= 1
}
}
}
}
}
rst
}
}
}
}