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).
题目大意：
给定一个n个整数的数组S，找出其中三个元素的和sum最接近目标target数，并返回和sum。
算法解析：
先循环遍历前n-2个元素，然后第二个元素（i+1）和第三个元素采用比较大小的方式按位增减。同时比较第i个、第i+1和length-1个元素的和sum与目标数target的大小，返回最接近目标数的sum。
代码如下：
- Java
class Solution {
public int threeSumClosest(int[] nums, int target) {
int length = nums.length;
int min = Integer.MAX_VALUE;
Arrays.sort(nums);
for (int i=0; i<length-2; i++) {
int begin = i+1;
int end = length-1;
if (i>0 && nums[i] == nums[i-1])
continue;
while (begin < end) {
int sum = nums[i] + nums[begin] + nums[end];
if (Math.abs(sum - target) < Math.abs(min))
min = sum-target;
else if (sum == target)
return target;
else if (sum < target)
begin++;
else
end--;
}
}
return min+target;
}
}
- Python
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @param {integer}
def threeSumClosest(self, nums, target):
length = len(nums)
min = 2147483647
nums.sort()
for i in range(length-2):
if i>0 and nums[i] == nums[i-1]:
continue
begin = i+1;end=length-1
while begin<end:
sum = nums[i]+nums[begin]+nums[end]
if abs(sum-target)<abs(min):
min = sum-target
if sum==target:
return target
elif sum<target:
begin+=1
else:
end-=1
return min+target
