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).
这道题目和前面的3Sum问题差不多,主要是改变了target值,只要在寻找target的过程中,不断更新最接近于target的值就可以了。
import sys class Solution: def threeSumClosest(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ n = len(nums) # 考虑特殊情况 if n < 3: return [] nums = sorted(nums) print(nums) i = 0 approx_target = sys.maxsize while i < n-2: left = i + 1 right = n - 1 while (left < right): val = nums[i] + nums[left] + nums[right] if val == target: return target elif abs(val-target) < abs(approx_target-target): approx_target = val elif val < target: left += 1 else: right -= 1 i += 1 return approx_target
Runtime: 136 ms, beats 97.28 %
近期评论