PRoblem:
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).思路: 這道題與前一道15題3Sum是相似的，直接用3Sum里提到的那兩種方法之一皆可。唯一不同的是還需要一個(gè)統(tǒng)計(jì)參數(shù)sum來(lái)記錄最接近target值的三個(gè)數(shù)和，然后每一次循環(huán)需要比較當(dāng)前三個(gè)數(shù)的和tmpsum與統(tǒng)計(jì)參數(shù)sum到target的絕對(duì)值，借此更新統(tǒng)計(jì)參數(shù)sum。
Solution:
class Solution(object): def threeSumClosest(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ ressum = 0 delta = 0 nums.sort() numslen = len(nums) if numslen < 3: return ressum else: ressum = nums[0]+nums[1]+nums[2] delta = abs(target - ressum) i = 0 for i in xrange(0,numslen-2): indexi = i+1 indexj = numslen-1 while indexi < indexj: tmp = target - nums[i] - nums[indexi] - nums[indexj] if abs(tmp) < delta: delta = abs(tmp) ressum = target - tmp if tmp > 0 : indexi += 1 elif tmp < 0: indexj -= 1 else: break return ressum新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
