3 Sum Closest

Question

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.

Thoughts

和 3 Sum 的思路接近，首先对原数组排序，随后将3 Sum 的题拆解为『1 Sum + 2 Sum』的题，对于 Closest 的题使用两根指针而不是哈希表的方法较为方便。

Solution

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 len(numbers) < 3:
            return None
        numbers.sort()
        results = []
        closest = 0
        minNum = sys.maxint
        for idx, num in enumerate(numbers):
            if idx != 0 and num == numbers[idx-1]:
                continue
            if idx > len(numbers) - 3:
                break
            twoTarget = target - num
            #only start with afterward elements
            twoSumResult = self.twoSumClosest(numbers[idx+1:], twoTarget)
            if twoSumResult:
                #index should start from idx + 1
                result = numbers[idx] + numbers[twoSumResult[0] + idx + 1] + numbers[twoSumResult[1] + idx + 1]
                if abs(result - target) < minNum:
                    minNum = abs(result - target)
                    closest = result
        return closest

    def twoSumClosest(self, numbers, target):
        length = len(numbers)
        minNum = sys.maxint
        index1 = 0
        index2 = length - 1
        p1 = 0
        p2 = length - 1
        while p1 < p2:
              s = numbers[p1] + numbers[p2]
              diff = abs(numbers[p1] + numbers[p2] - target)
              if diff < minNum:
                  minNum = diff
                  index1 = p1
                  index2 = p2
              if s < target:
                  p1 += 1
              else:
                  p2 -= 1
        return [index1, index2]