LeetCode:16. 最も近い三数の和

LeetCode:16. 最も近い三数の和
n個の整数を含む配列numsとターゲット値targetが与えられる.numsの3つの整数を見つけて、それらの和がtargetに最も近いようにします.この3つの数の和を返します.各入力セットに一意の答えしか存在しないと仮定します.
例:
nums = [-1,2,1,-4],target = 1
targetに最も近い3つの数の和は2です.(-1 + 2 + 1 = 2).
LeetCodeリンク
考え方:

ソート

最初からi番目の要素を固定し、2つのポインタをi+1、len(nums)-1から中間に遍歴し、targetとの距離が最も小さい組合せ

を探し、そして

現在およびtarget未満の場合、leftは右に移動する.現在およびtargetより大きい場合、rightは

左に移動する.

最適化:

現在の和がtargetに等しい場合、最小距離0となり、

に直接戻る.

付属コード(Python 3):

class Solution:
    def threeSumClosest(self, nums, target):
        if len(nums) < 3:
            return None
        
        nums.sort()                   #   
        dis = float('inf')            #      
        for i in range(len(nums)-2):
            left, right = i+1, len(nums)-1
            while left < right:
                cur = nums[i]+nums[left]+nums[right]
                if abs(cur-target) < dis:
                    dis = abs(cur-target)     #     
                    res = cur                 #      
                if cur < target:              
                    left += 1
                elif cur > target:
                    right -= 1
                else:                         #  cur=target，     0，    
                    return res
        return res

test = Solution()
nums_li = [[-1, 2, 1, -4], [1,1,-1,-1,3], [1,2,4,8,16,32,64,128]]
target_li = [1, 3, 82]
for nums, target in zip(nums_li, target_li):
    print(test.threeSumClosest(nums, target))

2
3
82