題目大概
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
- 1 題目大概是說給一個(gè)數(shù)組找到三個(gè)整數(shù)使其相加的和最接近所給的target
- 2 大概的思路就是說固定一個(gè)數(shù)帅刊，然后另外兩個(gè)數(shù)分別從左和右移動(dòng)
如果兩個(gè)數(shù)相加的和大于目標(biāo)和固定的那個(gè)數(shù)的距離，那么進(jìn)一步比較最左側(cè)的兩個(gè)數(shù)的和赖瞒，如果還是大于的話，則比較當(dāng)時(shí)的最近的距離和這個(gè)吧兔，并把最小的距離存儲(chǔ)
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
i = 0
size = len(nums)
if size < 3:
return 0
ans = nums[0] + nums[1] + nums[size - 1]
nums.sort()
while i < size - 2:
j = i + 1
k = size - 1
temp = target - nums[i]
while j < k:
if nums[j] + nums[k] == temp:
return target
if nums[j] + nums[k] > temp:
if nums[j] + nums[j + 1] >= temp:
if nums[j] + nums[j + 1] -temp < abs(ans - target):
ans = nums[i] + nums[j] + nums[j + 1]
break
tempans = nums[i] + nums[j] + nums[k]
if (tempans - target) < abs(ans - target):
ans = nums[i] +nums[j] +nums[k]
k -= 1
if nums[j] + nums[k] < temp:
if nums[k] + nums[k - 1] <= temp:
if abs(nums[k] + nums[k - 1] - temp) < abs(ans - target):
ans = nums[i] + nums[k - 1] + nums[k]
break
tempans = nums[i] + nums[j] +nums[k]
if abs(tempans - target) < abs(ans - target):
ans = nums[i] + nums[j] + nums[k]
j += 1
i += 1
if ans == target:
return target
return ans
