題目描述
給定一個(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è)置一個(gè)返回結(jié)果，用于更新最接近的目標(biāo)的三個(gè)數(shù)之和
同樣的操作绣硝，固定一個(gè)數(shù)蜻势，剩下來的二分查找
- 首先進(jìn)行數(shù)組排序撑刺，時(shí)間復(fù)雜度 O(nlogn)
- 在數(shù)組 nums 中鹉胖，進(jìn)行遍歷，每遍歷一個(gè)值利用其下標(biāo)i够傍，形成一個(gè)固定值 nums[i]
- 再使用前指針指向 start = i + 1 處甫菠，后指針指向 end = nums.length - 1 處，也就是結(jié)尾處
- 根據(jù) sum = nums[i] + nums[start] + nums[end] 的結(jié)果冕屯，判斷 sum 與目標(biāo) target 的距離寂诱，如果更近則更新結(jié)果 ans，同時(shí)判斷 sum 與 target 的大小關(guān)系安聘，因?yàn)閿?shù)組有序痰洒，如果 sum > target 則 end--，如果 sum < target 則 start++浴韭，如果 sum == target 則說明距離為 0 直接返回結(jié)果
整個(gè)遍歷過程丘喻，固定值為 n 次，雙指針為 n 次念颈，時(shí)間復(fù)雜度為 O(n^2)
總時(shí)間復(fù)雜度：O(nlogn) + O(n^2) = O(n 2)
class Solution:
def threeSumClosest(self, nums, target):
if not nums or len(nums) < 3:
return None
nums.sort()
ans = nums[0] + nums[1] + nums[2]
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
sums = nums[i] + nums[left] + nums[right]
if abs(target - ans) > abs(target - sums):
ans = sums
if sums > target:
right -= 1
elif sums < target:
left += 1
else:
return ans
return ans
AC16
