leetcode with python:16. 3Sum Closest

题目:

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

给定一阵列和目标值(target),找出阵列内最接近target的三数和
ex:input: nums = [-1,2,1,-4], target = 1=>output: 2
explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这题感觉像是15.的类题
于是我也採取类似的作法

class Solution:    def threeSumClosest(self, nums: List[int], target: int) -> int:        nums=sorted(nums)        diff=100000                if nums[0]+nums[1]+nums[2]>target: #前三项和>target就不用再找其他三和的可能            return nums[0]+nums[1]+nums[2]                if nums[-3]+nums[-2]+nums[-1]<target: #后三项和< target就不用再找其他三和的可能            return nums[-3]+nums[-2]+nums[-1]                            for i in range(len(nums)):            if i>0 and nums[i-1]==nums[i]:                continue            l=i+1            r=len(nums)-1            while l<r:                val=nums[l]+nums[r]+nums[i]                                    if val==target:                    return val                                    if abs(val-target)<diff:                    diff=abs(val-target)                    ans=val                                        if val>=target:                    r=r-1                    while l<r and nums[r]==nums[r+1]: #不断移动直到值变得不一样为止                        r=r-1                else:                    l=l+1                    while l<r and nums[l]==nums[l-1]: #不断移动直到值变得不一样为止                        l=l+1                      return ans

先将阵列排序,方便后续操作
diff纪录target和目前最接近三数和的差距

从阵列头开始,轮流将该位值当作固定值
而我们在固定值右侧的数列找出我们要和固定值相加最接近target的两个值
我有做几个加快效率的处理:
1.不考虑左侧因为这样会考虑重複的可能(先前就考虑过了)
2.若前三项和>target就不用再找其他三和的可能了
因为前三项和就是最接近target的三数和(其他和只会更大)
同样,若后三项和< target就不用再找其他三和的可能了
因为后三项和就是最接近target的三数和(其他和只会更小)
(阵列被排序过)
3.若固定值和上个固定值一样,就直接跳过(不用再次去考虑它的可能性)

确定固定值后,接下来是找另外两个值的部分:
设立两个指标(l,r)分别放在右侧数列的两端
设val=nums[l]+nums[r]+固定值

若val==target,就直接回传val(不会有更接近的值了)

若val小于target,则l往后走
让nums[l]变更大好让三数和更接近target(阵列被排序过)
但为了不要计算到重覆的可能,需要不断移动直到值变得不一样为止

若val大于target,则r往前走
让nums[r]变更小好让三数和更接近target(阵列被排序过)
但为了不要计算到重覆的可能,需要不断移动直到值变得不一样为止

若其中遇到target和val相聚小于diff
则我们找到了更接近的三数和
将val纪录为ans,同时将diff更新为两者差距

重複上述操作直到l和r碰面,再找下一个固定值

全部执行完后回传ans即可
最后执行时间837ms(faster than 31.75%)

哇讲了这么多结果效能却不尽人意
看了讨论区的解,才发现我的加速处理做得不够完善

class Solution:    def threeSumClosest(self, nums: List[int], target: int) -> int:        nums.sort()        ans = 100000        n = len(nums)        for i in range(n-2):            x = nums[i] + nums[-2] + nums[-1]            if x < target:                if abs(x-target) < abs(ans-target):                    ans = x                continue            y = nums[i] + nums[i+1] + nums[i+2]            if y > target:                if abs(y-target) < abs(ans-target):                    ans = y                break            a=nums[i]            k = i+1            e = n-1            while k < e:                s = nums[k] + nums[e]                if s==target-a:                    return target                if abs(s+a-target)<abs(ans-target):                    ans=s+a                if s < target-a:                    k += 1                else:                    e -= 1        return ans

可以看到此解核心概念跟我的其实差不多
但它在加速的处理上巧妙不少
以下是他做的处理:
1.当发现固定值和阵列末两项和小于target
则在此固定值只考虑该可能(固定值和阵列末两项和),接着用下一个固定值
因为该固定值下的其他三和可能只会更小
2.当发现固定值和固定值后两项和大于target
则在考虑该可能后(固定值和固定值后两项和),直接脱离迴圈
因为该可能后的其他三和可能只会更大
最后执行时间204ms(faster than 97.61%)

从执行时间可以看出
完善的加速处理让程式的效率一举提升数倍
在程式撰写上也不是应该被轻忽的一块

那我们下题见