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