題目:

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

從執行時間可以看出
完善的加速處理讓程式的效率一舉提升數倍
在程式撰寫上也不是應該被輕忽的一塊

那我們下題見