题目
三数之和 II
给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组，返回这三个数的和。
样例
例如S = [-1, 2, 1, -4] and target = . 和最接近1的三元组是 -1 + 2 + 1 = 2.
注意
只需要返回三元组之和，无需返回三元组本身
解题
和上一题差不多，程序也只是稍微修改了
public class Solution {
/**
* @param numbers: Give an array numbers of n integer
* @param target : An integer
* @return : return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] numbers ,int target) {
// write your code here
if(numbers == null)
return 0;
Arrays.sort(numbers);
int sum = Integer.MAX_VALUE ;
int numlen = numbers.length;
for( int i = 0;i< numlen ;i++){
int left = i + 1;
int right = numlen - 1;
while(left < right){
int tmpsum = numbers[i] + numbers[left] + numbers[right];
int tmpdist = tmpsum - target;
sum = Math.abs(tmpdist) > Math.abs(sum - target) ? sum:tmpsum;
if(tmpdist == 0){
return target;
}
if(tmpdist <0){
left++;
}else{
right--;
}
}
}
return sum;
}
}
Java Code
总耗时: 1504 ms
class Solution:
"""
@param numbers: Give an array numbers of n integer
@param target : An integer
@return : return the sum of the three integers, the sum closest target.
"""
def threeSumClosest(self, numbers, target):
# write your code here
if numbers == None:
return 0
numlen = len(numbers)
numbers.sort()
sum = 0
for i in range(numlen-1):
left = i + 1
right = numlen - 1
while left < right:
tmpsum = numbers[i] + numbers[left] + numbers[right]
tmpdist = tmpsum - target
if i==0:
sum = tmpsum
sum = sum if abs(tmpdist) > abs(sum-target) else tmpsum
if tmpdist == 0:
return target
if tmpdist < 0:
left +=1
else:
right -=1
return sum
Python Code
总耗时: 403 ms
