最接近的三數(shù)之和
題目來(lái)源：https://leetcode-cn.com/problems/3sum-closest
題目
給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target。找出 nums 中的三個(gè)整數(shù)，使得它們的和與 target 最接近宵荒。返回這三個(gè)數(shù)的和弥锄。假定每組輸入只存在唯一答案。
例如拴驮，給定數(shù)組 nums = [-1，2，1捧颅，-4], 和 target = 1.
與 target 最接近的三個(gè)數(shù)的和為 2. (-1 + 2 + 1 = 2).
解題思路
- 數(shù)組排序 + 雙指針；
- 對(duì)數(shù)組進(jìn)行排序较雕，初始化返回值
res為float('inf')正無(wú)窮碉哑，用以比較賦值； - 遍歷數(shù)組亮蒋，根據(jù)下面的步驟查找最接近的值：
- 先固定一個(gè)值
nums[i]扣典，定義雙指針L和R，分別指向固定值的下一位慎玖，以及最末尾的值贮尖； - 考慮邊界問題：
- 取包括固定值后續(xù)三位數(shù)之和（因?yàn)閿?shù)組已排序，
nums[i] + nums[L]+nums[L+1]）為當(dāng)前最小值 this_min凄吏，若是 this_min 比 target 大远舅，表示后續(xù)的數(shù)值無(wú)論怎么組合，值都會(huì)比 this_min 大痕钢，所以這里直接比較 this_min 和 res 跟 target 的差值的絕對(duì)值图柏，res 取較小的值，結(jié)束循環(huán)任连； - 取固定值與末尾最后的兩位數(shù)值之和為當(dāng)下的最大值 this_max蚤吹，若是 this_max 比 target 小，表示后續(xù)有更大可能接近 target 的值随抠。這里也比較 this_max 和 res 跟 target 的差值絕對(duì)值裁着，res 取較小值，然后跳過拱她。
- 取包括固定值后續(xù)三位數(shù)之和（因?yàn)閿?shù)組已排序，
- 不存在邊界問題時(shí)二驰，在雙指針之間進(jìn)行遍歷，計(jì)算固定值與雙指針指向的值之和 three_sum秉沼；
- 當(dāng) three_sum 等于 target 時(shí)桶雀，直接返回 target矿酵；
- 當(dāng) three_sum 不等于 target 時(shí)，比較 three_sum 和 res 與 target 的差值絕對(duì)值矗积，res 取較小值
- 當(dāng) three_sum 小于 target 時(shí)全肮，左指針往右邊移動(dòng)，尋找更接近的值棘捣，注意去重辜腺；
- 當(dāng) three_sum 大于 target 時(shí)，右指針往左移動(dòng)乍恐，尋找更接近的值评疗，注意去重；
- 循環(huán)過程取固定值時(shí)禁熏，考慮避免取到重復(fù)的固定值壤巷。
- 時(shí)間復(fù)雜度：
。
- 先固定一個(gè)值
代碼實(shí)現(xiàn)
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
# 先對(duì)數(shù)組進(jìn)行排序
nums.sort()
nl= len(nums)
# 將返回值初始化為正無(wú)窮
res = float('inf')
for i in range(nl-2):
# 去重
if i > 0 and nums[i] == nums[i-1]:
continue
# 定義雙指針
# 左邊指針指向固定值下一位
# 右邊指針指向末尾
L, R = i+1, nl-1
# 處理邊界的問題
this_min = nums[i] + nums[L] + nums[L+1]
# 數(shù)組已經(jīng)排序瞧毙，將連續(xù)三位數(shù)字作為當(dāng)下最小值
# 若是當(dāng)下最小的值比 target 還大，后面的數(shù)值與 target 的差值會(huì)越來(lái)越大
# 比較當(dāng)前最小值和返回值各自與 target 差值的大小寄症，賦值之后跳出循環(huán)
if this_min > target:
if (this_min - target) < abs(res - target):
res = this_min
break
# 將當(dāng)前值與最末尾兩位數(shù)值之和作為當(dāng)前的最大值
# 若是當(dāng)下最大值比 target 小宙彪，這里可以確定后續(xù)可能還有更接近的值
# 所以比較當(dāng)下最大值和返回值與 target 差值大小，賦值后有巧，直接跳過
this_max = nums[i] + nums[R-1] + nums[R]
if this_max < target:
if (target - this_max) < abs(res - target):
res = this_max
continue
# 不滿足上面的條件時(shí)
# 在兩指針的區(qū)間進(jìn)行遍歷
while L < R:
# 計(jì)算固定值與雙指針對(duì)應(yīng)值三者之和
three_sum = nums[i] + nums[L] + nums[R]
# 若結(jié)果等于 target释漆，直接返回 target
if three_sum == target:
return target
# 比較 three_num 和 res 分別與 target 的差值，res 取較小值
if abs(three_sum - target) < abs(res - target):
res = three_sum
# three_num 小于 target 時(shí)篮迎，左指針往右移動(dòng)男图，尋找更接近的值
if three_sum < target:
L += 1
# 去重
while L < R and nums[L] == nums[L-1]:
L += 1
# three_num 大于 target 時(shí)，右指針往左移動(dòng)甜橱，尋找更接近的值
else:
R -= 1
# 去重
while L < R and nums[R] == nums[R+1]:
R -= 1
return res
實(shí)現(xiàn)結(jié)果
實(shí)現(xiàn)結(jié)果
題外話
本題主要需要考慮的點(diǎn)在于邊界問題的處理逊笆。這一塊的處理，能夠很大程度上快速給出結(jié)果值岂傲。
以上就是本篇的主要內(nèi)容难裆。
歡迎關(guān)注微信公眾號(hào)《書所集錄》
