3Sum的一个变形。 3Sum链接(http://blog.csdn.net/lis_12/article/details/53207418)
#!/usr/bin/python # -*- coding: utf-8 -*- ''' 英文: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). ''' class Solution(object): def threeSumClosest(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ length = len(nums) if length < 3: return 'error' if length == 3: return sum(nums) pos = 0 nums.sort() result = sum(nums[:3]) while pos < length - 2: if nums[pos] == nums[pos - 1]: pos += 1 continue first = pos + 1 last = length - 1 while first < last: sum2 = nums[first] + nums[last] if sum2 + nums[pos] == target: return target if abs(sum2 + nums[pos] - target) < abs(result - target): result = sum2 + nums[pos] if sum2 + nums[pos] < target: first += 1 else: last -= 1 pos += 1 return result if __name__ == "__main__": s = Solution() print s.threeSumClosest([-1, 2, 1, -4],1)