coding = utf-8
'''
Created on 2015年11月9日
@author: SphinxW
'''
# 三数之和 II
#
# 给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组，返回这三个数的和。
# 样例
#
# 例如S = [-1, 2, 1, -4] and target = 1. 和最接近1的三元组是 -1 + 2 + 1 = 2.
# 注意
#
# 只需要返回三元组之和，无需返回三元组本身
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
numbers.sort()
fsum = numbers[0] + numbers[1] + numbers[2]
fdiff = abs(fsum - target)
for index in range(len(numbers)):
headIndex = 0
tailIndex = len(numbers) - 1
while headIndex < tailIndex:
if headIndex == index:
headIndex += 1
continue
if tailIndex == index:
tailIndex -= 1
continue
sum = numbers[index] + numbers[headIndex] + numbers[tailIndex]
diff = abs(sum - target)
if sum == target:
return sum
if fdiff > diff:
fsum = sum
fdiff = diff
if sum > target:
tailIndex -= 1
if sum < target:
headIndex += 1
return fsum
