LeetCode解析，第十六題：最接近的三數之和

LeetCode第十六題：最接近的三數之和

16：

英文題面：

Given an array nums of n integers 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。

Example:

Given array nums = ［-1， 2， 1， -4］， and target = 1。

The sum that is closest to the target is 2。 （-1 + 2 + 1 = 2）。

中文題面：

給定一個包括 n 個整數的陣列 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。

例如，給定陣列 nums = ［-1，2，1，-4］， 和 target = 1。

與 target 最接近的三個數的和為 2。 （-1 + 2 + 1 = 2）。

解析：

本題跟上一題實際上沒有區別，上一題是要求求和為0，本題求和為target。

實現邏輯還是如上一題，增加一個標記，記錄最小的差，若是當前的和與target的距離比記錄的最小值小，就將結果替換為當前的結果。

程式碼實現：

class Solution（object）：

def threeSumClosest（self， nums， target）：

“”“

：type nums： List［int］

：type target： int

：rtype： int

”“”

nums。sort（）

result = -100000000000

for i in range（len（nums））：

if i >= 1 and nums［i］ == nums［i-1］：

continue

start = i+1

end = len（nums）-1

while start < end：

if abs（nums［i］ + nums［start］ + nums［end］ - target） <= abs（result - target）：

result = nums［i］ + nums［start］ + nums［end］

if nums［i］ + nums［start］ + nums［end］ < target：

start += 1

elif nums［i］ + nums［start］ + nums［end］ > target：

end -= 1

else：

return target

return result