3 Sum Closest

题目描述

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).

解题方法

这道题和3 sum 类似，但是这里只需要找到一个组合并且return他们的sum，并且不用考虑重复的问题

所以每道题的需求和情况要分析好，并且这道题有pass一个target的变量，直接用3sum的code就会改变了target得到错误的解……而不是类似的题目就把code改一改……

Solution

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        numbers = nums
        if len(numbers) < 3:
            return []
        numbers.sort()
        result = sys.maxint
        minDiff = sys.maxint
        for idx, num in enumerate(numbers):
            t = target - num
            #only start with afterward elements
            curDiff, twoSumResults = self.twoSumClosest(numbers[idx+1:], t)
            if minDiff > curDiff:
               minDiff = curDiff
               result = num + numbers[idx+1+twoSumResults[0]] + numbers[idx+1+twoSumResults[1]]
        return result

    def twoSumClosest(self, numbers, target):
        # need to find all combinations now
        index1 = None
        index2 = None
        #record min Difference
        minDiff = sys.maxint
        start, end = 0, len(numbers) - 1
        while start < end:
                curSum = numbers[start] + numbers[end]
                curDiff = abs(curSum-target)
                if curDiff < minDiff:
                    minDiff = curDiff
                    index1 = start
                    index2 = end
                if curSum < target:
                    start += 1
                elif curSum > target:
                    end -= 1
                else:
                    break

        return minDiff, [index1, index2]